堆演算法

1. 堆排序時間復雜度是什麼

堆排序時間復雜度，主要在每次選取最大數之後，重新建堆的過程以及初始化堆過程。

堆排序是指利用堆積樹這種數據結構所設計的一種排序演算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。

堆是一個優先順序隊列，對於大頂堆而言，堆頂元素的權值最大。將待排序的數組建堆，然後不斷地刪除堆頂元素，就實現了排序。

堆的操作

在堆的數據結構中，堆中的最大值總是位於根節點（在優先隊列中使用堆的話堆中的最小值位於根節點）。堆中定義以下幾種操作：

最大堆調整（Max Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點。

創建最大堆（Build Max Heap）：將堆中的所有數據重新排序。

堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算。

2. 什麼是堆排序

【概念】堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即A[PARENT[i]] >= A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
【起源】
1991年的計算機先驅獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同發明了著名的堆排序演算法（ Heap Sort )。
【簡介】
堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特徵，使得在當前無序區中選取最大（或最小）關鍵字的記錄變得簡單。
（1）用大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區
② 再將關鍵字最大的記錄R[1]（即堆頂）和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key
③由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。
……
直到無序區只有一個元素為止。
（2）大根堆排序演算法的基本操作：
①建堆，建堆是不斷調整堆的過程，從len/2處開始調整，一直到第一個節點，此處len是堆中元素的個數。建堆的過程是線性的過程，從len/2到0處一直調用調整堆的過程，相當於o(h1)+o(h2)…+o(hlen/2) 其中h表示節點的深度，len/2表示節點的個數，這是一個求和的過程，結果是線性的O(n)。
②調整堆：調整堆在構建堆的過程中會用到，而且在堆排序過程中也會用到。利用的思想是比較節點i和它的孩子節點left(i),right(i)，選出三者最大(或者最小)者，如果最大（小）值不是節點i而是它的一個孩子節點，那邊交互節點i和該節點，然後再調用調整堆過程，這是一個遞歸的過程。調整堆的過程時間復雜度與堆的深度有關系，是lgn的操作，因為是沿著深度方向進行調整的。
③堆排序：堆排序是利用上面的兩個過程來進行的。首先是根據元素構建堆。然後將堆的根節點取出(一般是與最後一個節點進行交換)，將前面len-1個節點繼續進行堆調整的過程，然後再將根節點取出，這樣一直到所有節點都取出。堆排序過程的時間復雜度是O(nlgn)。因為建堆的時間復雜度是O(n)（調用一次）；調整堆的時間復雜度是lgn，調用了n-1次，所以堆排序的時間復雜度是O(nlgn)[2]
注意：
①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止
【特點】
堆排序（HeapSort）是一樹形選擇排序。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系（參見二叉樹的順序存儲結構），在當前無序區中選擇關鍵字最大（或最小）的記錄
【演算法分析】
堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。
平均性能：O(N*logN)。
其他性能：由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。堆排序是就地排序，輔助空間為O(1）。它是不穩定的排序方法。（排序的穩定性是指如果在排序的序列中，存在前後相同的兩個元素的話，排序前 和排序後他們的相對位置不發生變化）。

3. 堆排序的堆是怎麼建立的

堆排序，也叫二叉堆排序。
完全二叉樹：
1、左右子樹的節點數滿足 Ln/Rn=1
2、左右子樹高度滿足 Rh+1>=Lh>=Rh
3、子節點值統一比父節點大（小）。

最大堆：2叉樹的所有子節點都比父節點小。所以根節點是最大的。
最小堆：2叉樹的所有子節點都比父節點大。所以根節點是最小的。

建堆：假設最多有N個數據。開辟一段用來存這N個數據的空間。根節點位置為0。其子節點位置為1、2。所有子節點位置與父節點的位置（k）關系：k，2k+1，2k+2。 假設已經有了n個數據，那麼新數據自然放在n位（因為位置是從0開始），定義一個函數 shift_up() 用來調整新數據。它的功能是：將新數據與 (n-1)/2 位置的數據（新數據的父節點）比較，如果比父節點大，那麼就交換，繼續比較，直到它比父節點小。

重新建堆： 當取數據時，就是將根節點取出來。因為根節點是最大的，所以自然還要將其所有子節點進行調整，以保證剩下的數據的根節點是最大的。方法是：將最後一個數放到根節點位置（因為根節點取出後，根節點就空了），然後調用 shift_down()函數將其與1、2位置的數比較，如果比它大，則交換，然後繼續與2k+1，2k+2位置的比較，直到這兩個位置的數都比它小。

4. 堆排序演算法的實現

#include<stdio.h>
#include<malloc.h>
#include<time.h>
#define LISTSIZE 100
#define MORESIZE 100
#define overflow -1
typedef struct
{
int data;
int fre;
}Cell;
typedef struct {
Cell *elem;
long int length;
unsigned long int count1;
unsigned long int count2;
long int listsize;
}SqList;
SqList L1;
clock_t start,end;
FILE *p,*w;
int main (void)
{
void assign(Cell *a,Cell *b);
int LT(int a,int b);
void HeapSort (SqList &H);
void HeapAdjust (SqList &H,int s , int m);
void exchange(Cell *a,Cell *b);

//讀入

int time=0;
while(time<4)
{
switch (time)
{
case 0:
p=fopen("data01.txt","r");
w=fopen("sorted01.txt","w");
break;
case 1:
p=fopen("data02.txt","r");
w=fopen("sorted02.txt","w");
break;
case 2:
p=fopen("data03.txt","r");
w=fopen("sorted03.txt","w");
break;
case 3:
p=fopen("data04.txt","r");
w=fopen("sorted04.txt","w");
break;
}

L1.count1=0;
L1.count2=0;

time++;
L1.elem=(Cell *)malloc((LISTSIZE+1)*sizeof(Cell));
L1.listsize=LISTSIZE;
L1.length=1;
Cell *newbase;
while(!feof(p))
{

if (L1.length>L1.listsize){
newbase=(Cell *)realloc(L1.elem,(L1.listsize+MORESIZE+1)*sizeof(Cell));
if (!newbase)
return overflow;
L1.elem=newbase;
L1.listsize+=MORESIZE;}
fscanf (p,"%d (%d)\n",&((L1.elem+L1.length)->data),&((L1.elem+L1.length)->fre));
L1.length++;
}
L1.length--;
printf ("listsize=%d length=%d\n",L1.listsize,L1.length);

//排序
start=clock();//開始計時
HeapSort(L1); //堆排序
end=clock(); //結束計時
printf ("Time: %lf\n",(double)(end-start)/CLOCKS_PER_SEC);//輸出時間
for (int i=1;i<L1.length+1;++i)
fprintf (w,"%d (%d)\n",(L1.elem+i)->data,(L1.elem+i)->fre);
fprintf (w,"比較次數%u,移動次數%u\n",L1.count1,L1.count2);
printf ("比較次數%u,移動次數%u\n",L1.count1,L1.count2);
fprintf (w,"Copyright Reserved,Cheng Xuntao,NWPU");
fclose(p);
fclose(w);
}

return 0;

}
int LT(int a,int b)//比較函數
{L1.count1++;<br/> if (a<b){<br/> <br/> return 1;}
else return 0;
}
void assign(Cell *a,Cell *b)//賦值函數
{
a->data=b->data;
a->fre=b->fre;
L1.count2++;
}
void exchange(Cell *a,Cell *b)//交換記錄
{
int temp;
temp=a->data;
a->data=b->data;
b->data=temp;
temp=a->fre;
a->fre=b->fre;
b->fre=temp;
L1.count2+=3; //+=3
}
void HeapAdjust (SqList &H,int s , int m)//調節其成為堆
{
Cell *rc;
rc=(Cell *)malloc(sizeof(Cell));
int j;
assign(rc,H.elem+s); //暫存
for (j=2*s;j<=m;j*=2){ //沿值較大的孩子節點向下篩選
if (j<m && LT((H.elem+j)->data,(H.elem+j+1)->data ))
j++; //j為值較大的記錄的下標
if (!LT(rc->data,(H.elem+j)->data))
break; //rc應插入在位置s上
assign((H.elem+s),(H.elem+j));
s=j;
}
assign((H.elem+s),rc); //插入
}//HeapAdjust
void HeapSort (SqList &H) //堆排序
{
int i;
for (i=H.length/2;i>0;--i) //把L.elem[1...H.length]建成堆
HeapAdjust(H,i,H.length);
for (i=H.length;i>1;--i)
{
exchange(H.elem+1,H.elem+i); //將堆頂記錄和當前未經排序的子序列L.elem[i...i]中最後一個記錄相互交換
HeapAdjust(H,1,i-1); //重新調整其為堆
}
}//HeapSort

5. 建堆排序法中的堆是什麼

#include <stdio.h>
int swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
return 0;
}
void adjust(int *array, int i, int n)
{
int min, pos;
while(1) {
if((2*i+2) < n) {
min = array[2*i+1] < array[2*i+2] ? array[2*i+1] : array[2*i+2];
pos = array[2*i+1] < array[2*i+2] ? (2*i+1) : (2*i+2);
if(array[i] < min) { break; }
swap(&array[i], &array[pos]);
i = pos;
} else if((2*i+2) == n) {
min = array[2*i+1];
pos = 2*i+1;
if(array[i] < min) { break; }
swap(&array[i], &array[pos]);
i = pos;
} else {
break;
}
}
}
void heap_sort(int *array, int n)
{
//構建最小堆
for(int j=(n-1)/2; j>=0; --j) {
adjust(array, j, n);
}
//降序排列
for(int i=n; i>1; --i) {
swap(&array[0], &array[i-1]);
adjust(array, 0, --n);
}
}
int main()
{
int data[] = {12, 34, 23, 3, 1, 45, 87, 99};
heap_sort(data, 8);
for(int i=0; i<8; ++i) {
printf("%d ", data[i]);
}
printf("\n");
return 0;
}

6. 計算機二級的中的「堆排序法」是怎麼排的

堆排序就是將所有待排序的元素組成一個堆，然後不斷彈出堆頂的元素並調用函數維持堆序，直到所有元素均被彈出後，排序完成。被彈出的元素序列即一個有序數列。

一般做法是這樣：

當一個節點被插入時，將該節點放在堆的末尾（這是為了保證堆是完全二叉樹）然後將該節點與它的父節點比較，看該節點是否大於（或小於）其父節點，即判斷當前的堆是否滿足堆序。如果不滿足，則將該節點與其父節點交換。

再將該節點與其新的父節點做比較，依此類推，直到該節點不再需要與其父節點交換為止。（即滿足堆序時停止） 當一個根節點被彈出（即被從堆中刪除）時，將堆最尾部的節點移動到頭結點的位置，然後將該節點不斷與其子節點比較，如果不符合堆序則交換，直到符合堆序為止。

(6)堆演算法擴展閱讀：

堆的操作

堆排序是指利用堆這種數據結構所設計的一種排序演算法。堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

在堆的數據結構中，堆中的最大值總是位於根節點（在優先隊列中使用堆的話堆中的最小值位於根節點）。堆中定義以下幾種操作：

最大堆調整（Max Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點

創建最大堆（Build Max Heap）：將堆中的所有數據重新排序

堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算

7. 關於堆排序的演算法

error LNK2019: 無法解析的外部符號 "void __cdecl MAX_HEAPIFY(int *,int,unsigned int)" (?MAX_HEAPIFY@@YAXPAHHI@Z)，該符號在函數 "void __cdecl HEAPSORT(int *,unsigned int)" (?HEAPSORT@@YAXPAHI@Z) 中被引用

意思就是你那個函數沒有實現。

可以看到你的函數聲明和實現不一致：
void MAX_HEAPIFY(int *, int, size_t);
void MAX_HEAPIFY(int *arry, size_t i, size_t sz)
{}

參數類型不同，那就是不同的函數，C++的多態性。

修改聲明為：
void MAX_HEAPIFY(int *, size_t, size_t);

8. 堆排序過程

1，實用的排序演算法：選擇排序
（1）選擇排序的基本思想是：每一趟（例如第i趟，i=0，1，2，3，……n-2）在後面n-i個待排序元素中選擇排序碼最小的元素，作為有序元素序列的第i個元素。待到第n-2趟做完，待排序元素只剩下一個，就不用再選了。
（2）三種常用的選擇排序方法
1>直接選擇排序
2>錦標賽排序
3>堆排序
其中，直接排序的思路和實現都比較簡單，並且相比其他排序演算法，直接選擇排序有一個突出的優勢——數據的移動次數少。
（3）直接選擇排序簡介
1>直接選擇排序（select sort）是一種簡單的排序方法，它的基本步驟是：
1）在一組元素V[i]~V[n-1]中選擇具有最小排序碼的元素；
2）若它不是這組元素中的第一個元素，則將它與這組元素中的第一個元素對調；
3）在這組元素中剔除這個具有最小排序碼的元素，在剩下的元素V[i+1]~V[n-1]中重復執行1、2步驟，直到剩餘元素只有一個為止。
2>直接選擇排序使用注意
它對一類重要的元素序列具有較好的效率，這就是元素規模很大，而排序碼卻比較小的序列。因為對這種序列進行排序，移動操作所花費的時間要比比較操作的時間大的多，而其他演算法移動操作的次數都要比直接選擇排序來的多，直接選擇排序是一種不穩定的 排序方法。
3>直接選擇排序C++函數代碼

//函數功能，直接選擇排序演算法對數列排序
//函數參數，數列起點，數列終點
void dselect_sort(const int start, const int end) {
for (int i = start; i < end; ++i) {
int min_position = i;
for (int j = i + 1; j <= end; ++j) { //此循環用來尋找最小關鍵碼
if (numbers[j] < numbers[min_position]) {
min_position = j;
}
}
if (min_position != i) { //避免自己與自己交換
swap(numbers[min_position], numbers[i]);

（4）關於錦標賽排序
直接選擇排序中，當n比較大時，排序碼的比較次數相當多，這是因為在後一趟比較選擇時，往往把前一趟已經做過的比較又重復了一遍，沒有把前一趟的比較結果保留下來。
錦標賽排序（tournament sort）克服了這一缺點。它的思想與體育比賽類似，就是把待排序元素兩兩進行競賽，選出其中的勝利者，之後勝利者之間繼續競賽，再選出其中的勝利者，然後重復這一過程，最終構造出勝者樹，從而實現排序的目的。

2，堆排序的排序過程
（1）個人理解：堆排序是選擇排序的一種，所以它也符合選擇排序的整體思想。直接選擇排序是在還未成序的元素中逐個比較選擇，而堆排序是首先建立一個堆（最大堆或最小堆），這使得數列已經「大致」成序，之後只需要局部調整來重建堆即可。建立堆及重建堆這一過程映射到數組中，其實就是一個選擇的過程，只不過不是逐個比較選擇，而是藉助完全二叉樹來做到有目的的比較選擇。這也是堆排序性能優於直接選擇排序的一個體現。
（2）堆排序分為兩個步驟：
1>根據初始輸入數據，利用堆的調整演算法形成初始堆；
2>通過一系列的元素交換和重新調整堆進行排序。
（3）堆排序的排序思路
1>前提，我們是要對n個數據進行遞增排序，也就是說擁有最大排序碼的元素應該在數組的末端。
2>首先建立一個最大堆，則堆的第一個元素heap[0]具有最大的排序碼，將heap[0]與heap[n-1]對調，把具有最大排序碼的元素交換到最後，再對前面n-1個元素，使用堆的調整演算法siftDown(0,n-2)，重新建立最大堆。結果具有次最大排序碼的元素又浮到堆頂，即heap[0]的位置，再對調heap[0]與heap[n-2]，並調用siftDown(0，n-3)，對前n-2個元素重新調整，……如此反復，最後得到一個數列的排序碼遞增序列。
（4）堆排序的排序過程：
下面給出局部調整成最大堆的函數實現siftDown()，這個函數在前面最小堆實現博文中的實現思路已經給出，只需做微小的調整即可用在這里建立最大堆。

9. 堆排序是什麼

堆排序（HeapSort）是一樹形選擇排序。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系（參見二叉樹的順序存儲結構），在當前無序區中選擇關鍵字最大（或最小）的記錄
其過程為：
（1）用大根堆排序的基本思想

① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區

②
再將關鍵字最大的記錄R[1]（即堆頂）和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key

③由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。

……

直到無序區只有一個元素為止。

（2）大根堆排序演算法的基本操作：

① 初始化操作：將R[1..n]構造為初始堆；

②
每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後將新的無序區調整為堆（亦稱重建堆）。

注意：

①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。

②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止

10. 堆排序的比較次數

堆排序，顧名思義是通過直接選擇排序衍生而來的。直接選擇排序是直接從剩餘記錄中線性的查找最大記錄的方法，並沒有巧妙的利用前一輪查找所得到的信息，而堆排序，利用堆數據結構來保存剩餘記錄相對大小的信息，因而是更有效的選擇排序。
堆分為最大堆和最小堆，本篇我們通過最大堆來實現我們的功能。
最大堆需要滿足的條件： 堆中每個父節點中的數據項都要大於或等於其子節點中的數據項。
堆排序主要有兩個步驟：

對所有記錄建立一個最大堆。
取出堆頂的最大記錄與數組末端進行交換，最大記錄放在下標n-1的位置；
對剩餘堆記錄進行調整，再次形成一個最大堆；
再次取出對頂的最大記錄與數組末端進行交換，最大記錄放在下標n-2的位置；
不斷重復，直到堆為空，也就是排序完成。
示例數組如下：【49,38,65,97,76,13,27,49】
通過篩選法建最大堆的前提條件：

堆的初始位置從0開始，依次遞增；
若父結點的位置為i;則左孩子結點位置為2i+1；右孩子結點位置為2i+2;
篩選位置從最後一個非結點編號開始，也就是n/2-1向下取整。

初始堆如下：
初始堆

篩選位置從最後一個非結點編號開始，n=8,所以初始篩選位置為i=3，也就是i=97;
因為97>49,所以位置不變；然後繼續比較i,i–；
i=2時，因為13<27,且65>27，所以位置依舊不變。
i=1時，因為97>76，所以比較38和97，因為38<97所以交換位置；又因為38<49所以繼續交換位置，最後堆位置如下：
i=1時
i=0時，因為97>65,所以比較49和97,因為49<97,交換位置；又因為49<76,繼續交換位置，最後堆位置如下：
i=0時
到此位置，排序完成，堆變成了一個最大堆。
接下來則進行交換流程，將n-1位置的值與堆頂位置的值進行交換；

1、 i=7;交換位置7上的值和堆頂的值
交換1
交換完畢，再次調整除了i=7之外的堆元素，再次轉換成一個最大堆。
交換2

2、當i=6；交換位置6和堆頂的值，然後調整屬於的元素；
3、當i=5；交換位置5和堆頂的值，然後調整屬於的元素；
…
當i=1時；交換位置1和堆頂的值，交換流程到此結束，最後的堆如下：
end

以上是針對堆排序的分析流程