【數(shù)據(jù)結(jié)構(gòu)】堆及堆排序的實現(xiàn)（C語言）-創(chuàng)新互聯(lián)
目錄
前言
初始化
增刪?
由一個數(shù)組構(gòu)建堆
堆排序
TOPK問題
前言
我們都知道二叉樹是度為?2?的樹，如果在一個完全二叉樹里，所有的子結(jié)點都小于他的父結(jié)點，那么它就是堆。這樣的堆被稱之為大堆，反之則稱為小堆。
雖然我們畫出它的模型是完全二叉樹的樣子，但實際上堆的數(shù)據(jù)是存放在一個一維數(shù)組里的，不用驚慌，如下三個公式便可以解決我們于堆訪問的問題。歸根結(jié)底還是數(shù)學(xué)問題。
前面講過，堆的數(shù)據(jù)的存放在數(shù)組里面的，因此構(gòu)建的是一個順序表的結(jié)構(gòu)。并給予初始數(shù)值，因為將開辟空間一并放到?checkcapacity?里，所以這里就只是賦值成0而已。
typedef int heaptype;
typedef struct heap
{
heaptype* a;
int size;
int capacity;
}heap;//堆的初始化
void Heapinit(heap* hp)
{
hp->a = NULL;
hp->size = hp->capacity = 0;
}銷毀?
堆的銷毀十分簡單，直接把申請的空間全部釋放就可以了。
// 堆的銷毀
void HeapDestory(heap* hp)
{
assert(hp);
assert(hp->a);
free(hp->a);
hp->a = NULL; //回歸初始狀態(tài)
hp->size = hp->capacity = 0;
}插入數(shù)據(jù)
作為一個數(shù)組，插入數(shù)據(jù)最佳的地方應(yīng)該是數(shù)組的尾部。插入前還得檢查一下數(shù)組的大小是否夠用，否則擴容數(shù)組。
void checkcapacity(heap* hp)
{
if (hp->size == hp->capacity)
{
int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2; //初始化為4，否則大小翻倍
heaptype* narr = (heaptype*)realloc(hp->a, sizeof(heaptype) * newcapacity);
if (narr == NULL)
{
perror(realloc);
exit(-1);
}
hp->a = narr; //更新數(shù)據(jù)
hp->capacity = newcapacity;
}
}但僅僅插入是不行的，為了保證堆依然成立，我們還需要對數(shù)據(jù)的位置進行調(diào)整。（這里構(gòu)建的是小堆）?
我們應(yīng)該注意到的是，小堆的定義是每一個子結(jié)點都要大于它的父結(jié)點，這里我們只需要讓新插入的這個數(shù)據(jù)逐步地于它的父節(jié)點比較，小于則交換，大于就不再進行移動。
void adjustup(heap* hp)
{
int child = hp->size; //找到子結(jié)點的下標
int parent = (child-1)/2; //找到與該子結(jié)點對應(yīng)的父結(jié)點
while (child >0) //堆頂?shù)南聵藶?位于堆頂無需再調(diào)整
{
if (hp->a[child]< hp->a[parent]) //子結(jié)點小于父結(jié)點則交換
{
swap(&hp->a[child], &hp->a[parent]);
child = parent;
parent = (child - 1) / 2; //找當前位置的父結(jié)點
}
else
{
break; //大于則無需調(diào)整
}
}
}
把這些統(tǒng)合起來就完成了往堆里插入一個新值。
// 堆的插入(小堆)
void HeapPush(heap* hp, heaptype x)
{
assert(hp);
checkcapacity(hp);
hp->a[hp->size] = x;
adjustup(hp);
hp->size++;
}刪除堆頂數(shù)據(jù)
仔細思考，我們會發(fā)現(xiàn)若直接刪除堆頂是十分困難的，這時候我們不禁想：若堆頂?shù)哪莻€數(shù)據(jù)也在數(shù)組的尾部就好了。這無疑是為這個步驟提供了一個絕佳的思路?。?！我們可以把堆頂與堆底的數(shù)值交換，把最后面的值刪除之后，對堆頂?shù)臄?shù)據(jù)進行向下調(diào)整，由于原本堆底的值就是大的值，因此調(diào)整結(jié)束后其仍會回歸堆底。
void adjustdown(heaptype* a, int n, int root) //n是數(shù)組的大小
{
int parent = root; //找到向下調(diào)整的初始值
int child = parent * 2 + 1; //往下找其左孩子
while (parent< n)
{
if (child + 1< n && a[child] >a[child + 1]) //找孩子里最小的那個
{
child++;
}
if (child< n && a[parent] >a[child]) //父結(jié)點大于子結(jié)點就交換
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1; //找該結(jié)點對應(yīng)的子結(jié)點
}
else
{
break; //小于則停止調(diào)整
}
}
}刪除數(shù)組最后一個只需要調(diào)整size的值，并不需要對其進行其他調(diào)整。
// 堆頂?shù)膭h除
void HeapPop(heap* hp)
{
assert(hp);
assert(hp->a);
swap(&hp->a[hp->size - 1], &hp->a[0]);
hp->size--;
adjustdown(hp->a, hp->size, 0);
}堆頂數(shù)據(jù) 數(shù)據(jù)個數(shù) 判空
對基本數(shù)值判定就可以完成。
// 取堆頂?shù)臄?shù)據(jù)
heaptype HeapTop(heap* hp)
{
assert(hp);
assert(hp->a);
return hp->a[0];
}
// 堆的數(shù)據(jù)個數(shù)
int HeapSize(heap* hp)
{
assert(hp);
return hp->size;
}
// 堆的判空
bool HeapEmpty(heap* hp)
{
assert(hp);
if (hp->size)
{
return true;
}
return false;
}需要清楚的一件事是，我們能夠使用向下調(diào)整的前提是下面兩個堆都是小堆，因此若要由一個數(shù)組構(gòu)建堆并不只是一個勁地向下調(diào)整就可以解決的。
?
仔細一想，若我們從尾部向下調(diào)整上去，似乎結(jié)果就有所不同，我們只需要找到數(shù)組最后一個數(shù)的父結(jié)點，這時候向下調(diào)整就只會在這（2~3）個數(shù)直接尋找最小值放在該父結(jié)點上。之后找到最靠近這個父結(jié)點的另一父結(jié)點再次進行調(diào)整，直到到達堆頂完成堆的構(gòu)建。
void HeapCreate(heap* hp, heaptype* a, int n)
{
heaptype* narr = (heaptype*)malloc(sizeof(heaptype)*n); //開辟堆的空間
if (narr == NULL)
{
perror(malloc);
exit(-1);
}
hp->a = narr;
hp->size = 0;
hp->capacity = n;
for (int i = 0; i< n; i++) //導(dǎo)入原數(shù)組
{
checkcapacity(hp);
hp->a[i] = a[i];
hp->size++;
}
for (int i = (n - 1 - 1) / 2; i >= 0; i--) //從下往上逐步構(gòu)建小堆
{
adjustdown(hp, hp->size, i);
}
}我們都知道，在小堆內(nèi)堆頂?shù)臄?shù)據(jù)就是整個堆最小的，因此可以利用這個思想進行對數(shù)組的排序。把最小的數(shù)放在數(shù)組最后，其他的數(shù)繼續(xù)排序，直到全部完成。因此構(gòu)建大堆便排升序，構(gòu)建小堆則排降序。這樣子使得排序的實踐復(fù)雜度大大減小，達到提高運行效率的結(jié)果。
void HeapSort(heaptype* a, int n)
{
assert(a);
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
adjustdown(a, n, i); //構(gòu)建小堆排降序
}
int end = n-1; //找到數(shù)組尾端
while (end)
{
swap(&a[0], &a[end]); //最小值與最尾值交換
adjustdown(a, end, 0); //向下調(diào)整
end--; //把已調(diào)整完的值剔除于排序內(nèi)
}
}要求出大的幾個數(shù)，主要的思想便是先用前?k?個值創(chuàng)建一個小堆，若有值大于這個堆里最小的數(shù)（堆頂）則插入到堆里而剔除原堆頂?shù)脑?。遍歷完整個數(shù)組后，堆里剩下的就是大的?k?個數(shù)了。
void HeapSort(heaptype* a, int n)
{
assert(a);
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
adjustdown(a, n, i); //構(gòu)建小堆排降序
}
int end = n-1; //找到數(shù)組尾端
while (end)
{
swap(&a[0], &a[end]); //最小值與最尾值交換
adjustdown(a, end, 0); //向下調(diào)整
end--; //把已調(diào)整完的值剔除于排序內(nèi)
}
}
void PrintTopK(int* a, int n, int k)
{
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror(malloc);
exit(-1);
}
for (int i = 0; i< k; i++) //先取前k個數(shù)放到這個堆里面
{
minheap[i] = a[i];
}
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
adjustdown(minheap, k, i); //調(diào)整成一個小堆
}
for (int i = k; i< n; i++)
{
if (a[i] >minheap[0])
{
swap(&a[i], &minheap[0]); //大于堆頂就交換插進來
adjustdown(minheap, k, 0); //向下調(diào)整找到定位
}
}
for (int i = 0; i< k; i++)
{
printf("%d ", minheap[i]);
}
}這樣今天的堆與堆排序的講解就到這里結(jié)束了，如果有幫助到你還希望能給我一鍵三連，我們下次再見。
?
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
當前文章：【數(shù)據(jù)結(jié)構(gòu)】堆及堆排序的實現(xiàn)（C語言）-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://m.jiaotiyi.com/article/dophoi.html