一.堆排序 1.堆的概念及性質 1.1堆的概念
a. 堆是一種基本的數據結構。在這里我用數組來形容，在一個二叉堆的數組中，每一個元素（根）都要保證大于等于或小于等于另外兩個特定位置的元素（左右子樹）。同時相應的，這些元素（根）又要大于等于或小于等于另外兩個相應位置的元素（左右子樹），整個數據結構以此類推。如果我們將整個數據結構畫成樹狀結構，就能夠清晰地看出整個結構的樣子。
1.2堆的性質
a. 堆的邏輯結構一定是完全二叉樹，物理結構為順序表，用數組實現。
b. 任一根結點的值是其子樹所有結點的最大值或最小值
最大值時，稱為“最大堆”，也稱大根堆，如1.1中圖一；
在完全二叉樹中算法分析中實現堆排序c語言程序，任何一個子樹的最大值都在這個子樹的根結點
最小值時，稱為“最小堆”，也稱小根堆，如1.1中圖二；
在完全二叉樹中，任何一個子樹的最小值都在這個子樹的根結點。
c. 在物理結構上，如果父親節點的位置為k,那么它的左右孩子節點分別為2k+1和 2k+2,那么如果孩子節點位置為k,則父親節點為（k-1) / 2。
二.向下調整和向上調整兩大算法 1. 向下調整算法 2.1 向下調整算法基本思路
a.若想將其調整為小堆，那么根節點的左右子樹必須是小堆。
b.若想將其調整為大堆，那么根節點的左右子樹必須是大堆。
c.向下調整算法的基本思路（小堆）
1.從根節點處開始，選出左右孩子中值較小的孩子。
2.讓小的孩子與其父親進行比較。
若小孩子比父親小，則該孩子與其父親的位置進行交換。并將原來小的孩子的位置當做父親繼續向下進行調整，直到調整到葉子節點為止。
若調整中間小的孩子比父親大，則不需要繼續向下調整了，整個樹已經為小堆了，調整完成。
圖片示例：
堆（小堆）的向下調整算法代碼實現：
void AdjustDown(HPDataType* a,int size,int root)
{
int parent = root;
int child = 2 * parent + 1;
//假設左孩子為較小的孩子
while (child < size)
{
if (child + 1 < size && a[child] > a[child + 1])
{
child++;
}
//如果右孩子存在，且右孩子小于左孩子，則假設不成立，右孩子為較小的孩子
if (a[parent] > a[child])
{
Swap(&a[child], &a[parent]);
//交換
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
使用堆的向下調整算法，最壞的情況下（即一直需要交換結點），需要循環的次數為：h - 1次（h為樹的高度）。而h = log2(N+1)（N為樹的總結點數）。所以堆的向下調整算法的時間復雜度為：O(logN) 。
2. 向上調整算法 2.2 向上調整的基本思路
a.若想將其調整為小堆，那么除該節點外，整個樹必須為小堆。
b.若想將其調整為大堆，那么除該節點外，整個樹必須為大堆。
c.向下調整 的基本思路（大堆）
1.由該節點找到其父親節點。
若該節點（孩子節點）的值大于其父親節點的值，兩個節點的位置發生交換，再把原來父親節點的位置當做孩子節點，繼續向上調整，直到樹的根為止。
若中間調整過程中，孩子節點的值小于其父親節點的值，則不需要在向上調整了，整個樹已經為大堆了，調整完成。
圖片示例：
堆（大堆）的向下調整算法代碼實現：
void AdjustUp(HPDataType* a,int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
//交換
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
使用堆的向上調整算法，最壞的情況下（即一直需要交換結點），需要循環的次數為：h - 1次（h為樹的高度）。而h = log2(N+1)（N為樹的總結點數）。所以堆的向上調整算法的時間復雜度為：O(logN) 。
三.堆的實現（小堆） 1.頭文件包含
#pragma once
#include
//堆的銷毀
void HeapDestroy(Heap* HP);
//堆的打印
void HeapPrint(Heap* php)
//向堆存放數據
void HeapPush(Heap* HP,HPDataType x);
//刪除堆中元素
void HeapPop(Heap* HP);
//獲取堆頂元素
HPDataType HeapTop(Heap* hp);
// 堆的數據個數
int HeapSize(Heap* HP);
// 堆的判空
int HeapEmpty(Heap* HP);
2. 接口實現
#include"heap.h"
void HeapInit(Heap* HP)
{
assert(HP);
HP->a = NULL;
HP->size = HP->capacity = 0;
}
void HeapDestroy(Heap* HP)
{
assert(HP);
assert(HP->a);
free(HP->a);
HP->a = NULL;
HP->capacity = HP->size = 0;
}
void HeapPrint(Heap* php)
{
assert(php);
for (size_t i = 0; i < php->size; ++i)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
void Swap(HPDataType* child, HPDataType* parent)
{
HPDataType tmp = *child;
*child = *parent;
*parent = tmp;
}
void AdjustUp(HPDataType* a,int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPush(Heap* HP,HPDataType x)
{
assert(HP);
if (HP->size == HP->capacity)
{
int newcapacity = HP->capacity == 0 ? 4 : 2 * HP->capacity;
HPDataType* tmp = (HPDataType*)realloc(HP->a,newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
printf("malloc is fail\n");
exit(-1);
}
HP->a = tmp;
HP->capacity = newcapacity;
}
HP->a[HP->size] = x;
HP->size++;
AdjustUp(HP->a, HP->size - 1);
}
void AdjustDown(HPDataType* a,int size,int root)
{
int parent = root;
int child = 2 * parent + 1;
while (child < size)
{
if (child + 1 < size && a[child] > a[child + 1])
{
child++;
}
if (a[parent] > a[child])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void HeapPop(Heap* HP)
{
assert(HP);
Swap(&HP->a[0], &HP->a[HP->size - 1]);
HP->size--;
AdjustDown(HP->a,HP->size,0);
}
HPDataType HeapTop(Heap* HP)
{
assert(HP);
return HP->a[0];
}
int HeapSize(Heap* HP)
{
assert(HP);
return HP->size;
}
int HeapEmpty(Heap* HP)
{
assert(HP);
return HP->size == 0;
}
四.任意樹調整為堆（小堆為例） 1.向下調整法建堆
如果左右子樹不是小堆，就不能直接使用向下調整算法了！那么如何才能將一個任意的樹調整為堆呢？該怎么辦？？？
其實答案很簡單，我們只需要從倒數第一個非葉子結點開始，從后往前，按下標，依次作為根去向下調整即可。（倒數第一個非葉子節點一定是最后一個葉子節點的父親）
a.邏輯結構
b.物理結構
int a[] = {3,5,2,7,8,6,1,9,4,0};
c.建堆代碼：
for(int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown（a,n,i）;
}
那么建堆的時間復雜度又是多少呢？
當結點數無窮大時，完全二叉樹與其層數相同的滿二叉樹相比較來說，它們相差的結點數可以忽略不計，所以計算時間復雜度的時候我們可以將完全二叉樹看作與其層數相同的滿二叉樹來進行計算。
我們計算建堆過程中總共交換的次數：
T ( n ) = 1 × ( h ? 1 ) + 2 × ( h ? 2 ) + . . . + 2h-3 × 2 + 2h-2 × 1
兩邊同時乘2得：
2 T ( n ) = 2 × ( h ? 1 ) + 2 2 × ( h ? 2 ) + . . . + 2h-2× 2 + 2h-1 × 1
兩式相減得：
T ( n ) = 1 ? h + 2 1 + 2 2 + . . . + 2 h-2 + 2 h-1
運用等比數列求和得：
T ( n ) = 2h ? h ? 1
由二叉樹的性質，有N = 2h ? 1和 h = log ?2 ( N + 1 )， 于是
T ( n ) = N ? log ?2 ( N + 1 )
用大O的漸進表示法：
T ( n ) = O ( N )
總結一下：
堆的向下調整算法的時間復雜度：T ( n ) = O ( log ? N ) 。
建堆的時間復雜度：T ( n ) = O ( N ) 。
2.堆（大堆）排序
那么堆建好后，如何進行堆排序呢？
步驟如下：
(1) 將堆頂數據與堆的最后一個數據交換，然后對根位置進行一次堆的向下調整算法分析中實現堆排序c語言程序，但是調整時被交換到最后的那個最大的數不參與向下調整。
(2) 完成步驟1后，這棵樹除最后一個數之外，其余數又成一個大堆，然后又將堆頂數據與堆的最后一個數據交換，這樣一來，第二大的數就被放到了倒數第二個位置上，然后該數又不參與堆的向下調整…反復執行下去，直到堆中只有一個數據時便結束。此時該序列就是一個升序。
void HeapSort1(int* a, int n)
{
//建大堆排升序
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
HeapDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
HeapDown(a, end, 0);
end--;
}
}
時間復雜度O(N*logN)