二叉樹概念博客：http://t.csdn.cn/XIW84
目錄
1. 了解堆
1.1 堆的概念
1.2 堆的性質(zhì)：
1.3 堆的結(jié)構(gòu)圖片
1.3.1 小堆
1.3.2 大堆
2. 堆的實現(xiàn)
2.1 插入數(shù)據(jù)進堆
2.2 向上調(diào)整函數(shù)
2.3 堆的刪除
2.4 向下調(diào)整
3. 堆的應(yīng)用
3.1 建堆（兩種方式）
3.1.1 建堆方式1
3.1.2 建堆方式2
3.2 堆排序?
3.3 堆的TOP—K問題
1. 了解堆
1.1 堆的概念
1.2 堆的性質(zhì)：
堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；
堆總是一棵完全二叉樹。
1.3 堆的結(jié)構(gòu)圖片
1.3.1 小堆
?滿足下面條件的是小堆
1.3.2 大堆
滿足下面條件的是大堆
?注意不一定是從大到小、從小到大存儲的?。?！
堆有什么作用呢？
下面來細講，別走開?。。?/span>
2. 堆的實現(xiàn)
2.1 插入數(shù)據(jù)進堆
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newcapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}注意點?。?！
假如一開始我們的堆是小堆，但是在插入數(shù)據(jù)以后要保持還是小堆，要將插入的數(shù)據(jù)的大小和它的父親進行比較，比較的兩種情況：
1. 如果插入的數(shù)據(jù)比父親還要大，那就不需要調(diào)整
2.?如果插入的數(shù)據(jù)比父親還要小，那就需要調(diào)整? ?
? 如果需要調(diào)整，我們就要使用向上調(diào)整算法，保持插入數(shù)據(jù)后的堆還是小堆
2.2 向上調(diào)整函數(shù)
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;//求出插入數(shù)據(jù)的父親位置下標
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;//將父親的下標給孩子，向上調(diào)整
parent = (child - 1) / 2;//再算出此時插入數(shù)據(jù)的父親下標
}
else
{
break;
}
}
}
2.3 堆的刪除
能不能使用覆蓋刪除呢—不能?。?！
使用覆蓋刪除，會打亂父子之間的下標關(guān)系，父子關(guān)系就會全部亂掉，因此我們使用下面的方法來刪除數(shù)據(jù)
1. 先將下標為0位置的數(shù)據(jù)和下標最大的數(shù)據(jù)進行交換
2. 然后直接size--
3. 然后還需要使用向下調(diào)整算法，把堆再調(diào)整為小堆
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&(php->a[0]), &(php->a[php->size - 1]));1.交換
php->size--;//2. 刪除堆頂元素
AdjustDwon(php->a, php->size, 0);//向下調(diào)整，保證還是小堆
}2.4 向下調(diào)整
void AdjustDwon(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
// 選出左右孩子中小那個
//這里的if里面的判斷大小盡量寫成小于是小堆，大于是大堆
if (child+1 < size && a[child+1] < a[child])
{
++child;
}
// 孩子跟父親比較
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}3. 堆的應(yīng)用
3.1 建堆（兩種方式）
3.1.1 建堆方式1
利用插入元素的方式，向上調(diào)整建堆?
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
//if (a[child] < a[parent])
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
/
void HeapSort(int* a, int n)//傳一個數(shù)組過來，還有元素個數(shù)
{
// 建堆方式1：O(N*logN)
for (int i = 1; i < n; ++i)
{
AdjustUp(a, i);//從插入的第二個元素開始
}
}建堆方式1的時間復(fù)雜度 ——錯位相減法
3.1.2 建堆方式2
利用向下調(diào)整建堆
方法：找到最后一個元素的父親，并從這個位置開始向下調(diào)整?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
void HeapSort(int* a, int n)
{
// 建堆方式2：O(N)
for (int i = (n-1-1)/2; i >= 0; --i)
{
AdjustDwon(a, n, i);
}
// O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
--end;
}
}建堆方式2的時間復(fù)雜度——錯位相減法
3.2 堆排序?
排升序，建大堆，再向下調(diào)整
為什么建大堆呢？
建大堆，堆頂元素是最大的數(shù)，讓堆頂元素和最后一個元素交換，再向下調(diào)整，注意：這里向下調(diào)整時是調(diào)整的數(shù)組大小-1個，也就是調(diào)整剛剛交換下來前面的數(shù)據(jù)
排降序，建小堆，再向下調(diào)整
void HeapSort(int* a, int n)
{
// 建堆方式2：O(N)
for (int i = (n-1-1)/2; i >= 0; --i)
{
AdjustDwon(a, n, i);
}
// O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);//這里的end是9，傳過去向下調(diào)整的元素個數(shù)也是9，
//就不會調(diào)整剛剛從堆頂傳下來的數(shù)據(jù)
AdjustDwon(a, end, 0);
--end;
}3.3 堆的TOP—K問題
TOP-K問題：即求數(shù)據(jù)結(jié)合中前K個最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。
比如：專業(yè)前10名、世界500強、富豪榜、游戲中前100的活躍玩家等。
實現(xiàn)思路：?
這樣空間復(fù)雜度非常小
注意：
? ? ? ? ? ?求前k個最大的數(shù)，是建小堆
? ? ? ? ? ?解釋：由于建立的前k個數(shù)是小堆，后面n-k個數(shù)都可能比對頂?shù)臄?shù)值大，比堆頂?shù)脑卮?，就替換堆頂?shù)脑?，然后再向下調(diào)整，保持前k個數(shù)是小堆，然后再比較····
? ? ? ? ? ?求前k個最小的數(shù)，是建大堆（同上）
?代碼實現(xiàn)：
void PrintTopK(int* a, int n, int k)
{
// 1. 建堆--用a中前k個元素建堆
int* kMinHeap = (int*)malloc(sizeof(int)*k);
assert(kMinHeap);
for (int i = 0; i < k; ++i)//將a數(shù)組里面前10個數(shù)賦值給KMinHeap
{
kMinHeap[i] = a[i];
}
for (int i = (k - 1 - 1) / 2; i >= 0; --i)//向下調(diào)整建堆，建立k個數(shù)的小堆
{
AdjustDwon(kMinHeap, k, i);
}
// 2. 將剩余n-k個元素依次與堆頂元素交換，不滿則則替換
for (int j = k; j < n; ++j)
{
if (a[j] > kMinHeap[0])
{
kMinHeap[0] = a[j];
AdjustDwon(kMinHeap, k, 0);//再向下調(diào)整，保持前k個數(shù)是小堆
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", kMinHeap[i]);
}
printf("\n");
}
void TestTopk()
{
//隨機生成一萬個數(shù)字，每個數(shù)字%1百萬，這一萬都是比一百萬小的數(shù)字，
//我們將其中的10個數(shù)改為比一百萬大的值
int n = 10000;
int* a = (int*)malloc(sizeof(int)*n);
srand(time(0));
for (int i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[120] = 1000000 + 5;
a[99] = 1000000 + 6;
a[0] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
PrintTopK(a, n, 10);
}
本文講的是二叉樹的順序存儲結(jié)構(gòu)（堆）的實現(xiàn)，下期我們來講二叉樹的鏈式存儲結(jié)構(gòu)，到時候記得來支持小余哦?。?！文章來源：http://www.zghlxwxcb.cn/news/detail-441177.html
如果覺得文章不錯，期待你的一鍵三連哦，你個鼓勵是我創(chuàng)作的動力之源，讓我們一起加油，頂峰相見！??！文章來源地址http://www.zghlxwxcb.cn/news/detail-441177.html
到了這里，關(guān)于深入淺出堆—C語言版【數(shù)據(jù)結(jié)構(gòu)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
