關于堆的知識
- 什么是堆
- 堆的向下排序演算法
- 代碼實作
- 如何對無規律的陣列進行堆的向下排序演算法使其成為堆
- 代碼實作
- 堆的向上調整演算法
- 實作代碼
- 建堆的時間復雜度
- 堆排序
- 代碼實作
- 堆的實作
- 初始化堆
- 銷毀堆
- 列印堆
- 堆的插入
- 堆的洗掉
- 獲取堆頂的元素
- 堆的判空
- 堆中元素的個數
什么是堆
可能概念講的不是很好理解，下面我們看兩幅圖，
那么問題來了？我們給的一組資料總不可能就那么巧吧，正好是有序的，這時就要介紹一個演算法了：堆的向下排序演算法，使一組不是那么有規律的數字也變成堆，
堆的向下排序演算法
int array[] = {27,15,19,18,28,34,65,49,25,37};
從這組資料中你能發現什么特點嗎？也不難發現，這組資料除了根節點，左右子樹都是小堆，這也是使用向下調整演算法的前提：
左右子樹必須是一個堆，才能調整，
下面我們來看調整的程序：讓根和它孩子中較小的孩子進行交換，然后孩子的位置換成父親節點，父親節點再找孩子節點，以此達到迭代的目的，
代碼實作
void swap(int* children, int* gen)
{
int temp = *children;
*children = *gen;
*gen = temp;
}
//建的小堆
void Heapdown(int *a, int n,int gen)
{
//假設法：假設目標值是你想要的值
int children = gen * 2 + 1;
while (children<n)
{
if (children+1<n&&a[children + 1] < a[children])
{
children++;
}
if (a[children] <= a[gen])
{
//要傳地址，不然影響不到外面
swap(&a[children],&a[gen]);
}
else
{
break;
}
gen = children;
children = gen * 2 + 1;
}
}
注意點：
1.巧用假設法，假設目標值為小的孩子，這樣可以大大簡化代碼，
2.要保證children+1<n以防陣列越界，
3.swap傳參的時候要傳地址，這樣才能影響到外面，
如何對無規律的陣列進行堆的向下排序演算法使其成為堆
到這兒， 相信聰明的你一定會問了？如果給的一組資料完全沒有規律可循了，那怎么辦了？
下面我們就來看看堆的向下排序的妙處：從后往前排，來解決這個問題，
其實這種思想我是這樣理解的：如果你想讓整棵樹都成為小堆，那么你就要讓其中各個部分變成小堆，從第一個父親節點開始逐漸調整，
代碼實作
void swap(int* children, int* gen)
{
int temp = *children;
*children = *gen;
*gen = temp;
}
//建的小堆
void Heapdown(int *a, int n,int gen)
{
//假設法：假設目標值是你想要的值
int children = gen * 2 + 1;
while (children<n)
{
if (children+1<n&&a[children + 1] < a[children])
{
children++;
}
if (a[children] <= a[gen])
{
//要傳地址，不然影響不到外面
swap(&a[children],&a[gen]);
}
else
{
break;
}
gen = children;
children = gen * 2 + 1;
}
}
int main()
{
int a[] = { 27, 15, 18, 13, 19, 21, 28, 29, 1, 2 };
int sz = sizeof(a) / sizeof(int);
int gen = (sz - 1 - 1) / 2;
int i = gen;
for (i = gen; i >= 0; i--)
{
//向下調整演算法，用來建堆
Heapdown(a, sz, i);
}
for (i = 0; i < sz; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
注意點：這里要注意的就是，父親節點與孩子節點之間的關系，
堆的向上調整演算法
既然堆有向下調整演算法，那么相對的也就有向上調整演算法，
當我們在一個堆的末尾插入一個資料后，需要對堆進行調整，使其仍然是一個堆，這時需要用到堆的向上調整演算法，
向上調整演算法的基本思想（以建小堆為例）：
1.將目標結點與其父結點比較，
2.若目標結點的值比其父結點的值小，則交換目標結點與其父結點的位置，并將原目標結點的父結點當作新的目標結點繼續進行向上調整，若目標結點的值比其父結點的值大，則停止向上調整，此時該樹已經是小堆了，
實作代碼
void AdjustUp(int* a,int child)
{
int father = (child - 1) / 2;
while (child!=0)
{
if (a[child] > a[father])
{
swap(&a[child], &a[father]);
child = father;
father = (child - 1) / 2;
}
else
{
break;
}
}
}
注意點：
while里面的判斷條件最好不要寫上father>=0，這樣寫只不過是碰巧能過而已，因為到最后一次的時候（0-1）/2等于0，進回圈0和0比，走的是break，因此這樣跳出了回圈，
建堆的時間復雜度
到這人你可能會問了？那么建堆的時間復雜度是多少了？
下面我們來看看推導程序（可能字寫的有些丑，大家請見諒）：
注意上圖是以向下調整演算法為例的，其實向上調整演算法建堆的時間復雜度也為O(N)，
堆排序
前面介紹的東西其實都是為了堆排序做鋪墊的，
下面我們來想一個問題：如果我們把一組資料排成降序，應該是用小堆還是大堆了？ 相信很多人肯定會首先回答：大堆，因為大堆的0號位數字為最大的數，然后再找次大的數字，但這樣的話會有一個很嚴重的問題：那就是堆的結構被破壞了，
下面我們來看一個例子：
當我們再次找最大的資料時，我們發現這時堆的結構已經被破壞了，如果你要繼續找的話，還要將他進行建堆，效率低，
正確的做法應該是建小堆：
代碼實作
void swap(int* children, int* gen)
{
int temp = *children;
*children = *gen;
*gen = temp;
}
//建的小堆
void Heapdown(int *a, int n,int gen)
{
//假設法：假設目標值是你想要的值
int children = gen * 2 + 1;
while (children<n)
{
if (children+1<n&&a[children + 1] < a[children])
{
children++;
}
if (a[children] <= a[gen])
{
//要傳地址，不然影響不到外面
swap(&a[children],&a[gen]);
}
else
{
break;
}
gen = children;
children = gen * 2 + 1;
}
}
int main()
{
int a[] = { 27, 15, 18, 13, 19, 21, 28, 29, 1, 2 };
int sz = sizeof(a) / sizeof(int);
int gen = (sz - 1 - 1) / 2;
int i = gen;
for (i = gen; i >= 0; i--)
{
//向下調整演算法，用來建堆
Heapdown(a, sz, i);
}
//堆排序,用小堆的話排的就是降序
//用大堆的話排的就是升序
int end = sz - 1;
for (end = sz - 1; end > 0;)
{
swap(&a[0],&a[end]);
end--;
sz--;
for (i = (sz - 1 - 1) / 2; i >= 0; i--)
{
Heapdown(a, sz, i);
}
}
sz = sizeof(a) / sizeof(int);
for (i = 0; i < sz; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
注意點：
1.這里要注意sz和end大小的調整，
2.這里要注意這種思想的運用，在之后的學習中，這種思想很重要，
堆的實作
初始化堆
首先，必須創建一個堆型別，該型別中需包含堆的基本資訊：存盤資料的陣列、堆中元素的個數以及當前堆的最大容量，
typedef int HpDataType;
typedef struct Heap
{
HpDataType* a;
int size;
int cap;
}Hp;
然后我們需要一個初始化函式，對剛創建的堆進行初始化，注意在初始化期間要將傳入資料建堆，
void HpInit(Hp* php,int *b,int sz)
{
assert(php);
HpDataType* new = (HpDataType*)malloc(sizeof(HpDataType)*sz);
if (new == NULL)
{
printf("malloc failed\n");
exit(-1);
}
php->a = new;
int i = 0;
//for (i = 0; i < sz; i++)
//{
// php->a[i] = b[i];
//}
//另外一種快速的傳遞方法
//拷貝資料到堆中
memcpy(php->a, b, sizeof(HpDataType)*sz);
php->size = sz;
php->cap = sz;
int gen = (sz - 2) / 2;
for (i = gen; i >= 0; i--)
{
Adjustdown(php->a, sz,i);
}
}
銷毀堆
為了避免記憶體泄漏，使用完動態開辟的記憶體空間后都要及時釋放該空間，所以，一個用于釋放記憶體空間的函式是必不可少的，
void HpDestory(Hp* php)
{
assert(php);
//因為是連續的空間，所以可以這樣釋放，跟順序表一樣
free(php->a);
php->a = NULL;
php->size = php->cap = 0;
}
列印堆
把堆里面的資料列印出來，可以方便我們觀察，
void HpPrint(Hp php)
{
int i = 0;
for (i = 0; i <php.size; i++)
{
printf("%d ", php.a[i]);
}
printf("\n");
}
注意：這里我們這按堆在記憶體中的物理結構列印的，并沒有按邏輯結構（也就是數的形狀來列印），
堆的插入
資料插入時是插入到陣列的末尾，即樹形結構的最后一層的最后一個結點，所以插入資料后我們需要運用堆的向上調整演算法對堆進行調整，使其在插入資料后仍然保持堆的結構，
void HpPush(Hp* php, HpDataType x)
{
assert(php);
//擴容
if (php->size == php->cap)
{
HpDataType* new = (HpDataType*)realloc(php->a,sizeof(HpDataType)*(php->cap)*2);
if (new == NULL)
{
printf("realloc failed\n");
exit(-1);
}
php->a = new;
php->cap *= 2;
}
//注意這兒寫的時候的順序，要先調整一下，再讓size++，如果反過來的話，你傳參進去的size就會多加了一下
php->a[php->size] = x;
AdjustUp(php->a, php->size);
php->size++;
}
注意：寫的時候要先寫向上調整演算法，再寫size++，不然參進去的size就會多加了一下
堆的洗掉
堆的洗掉，洗掉的是堆頂的元素，但是這個洗掉程序可并不是直接洗掉堆頂的資料，而是先將堆頂的資料與最后一個結點的位置交換，然后再洗掉最后一個結點，再對堆進行一次向下調整，
原因：我們若是直接洗掉堆頂的資料，那么原堆后面資料的父子關系就全部打亂了，需要全體重新建堆，時間復雜度為O ( N ) O(N)O(N)，若是用上述方法，那么只需要對堆進行一次向下調整即可，因為此時根結點的左右子樹都是小堆，我們只需要在根結點處進行一次向下調整即可，時間復雜度為O ( log ? ( N ) )
void HpPop(Hp* php)
{
assert(php);
assert(!HpEmpty(*php));
swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
Adjustdown(php->a, php->size, 0);
}
獲取堆頂的元素
HpDataType HpTop(Hp php)
{
return php.a[0];
}
堆的判空
bool HpEmpty(Hp php)
{
return php.size == 0;
}
堆中元素的個數
int HpSize(Hp php)
{
return php.size;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297144.html
標籤：其他
上一篇：C語言庫函式之----qsort函式決議（快速排序）
下一篇：動圖演示堆排序