玩轉C語言數組，一圖掌握數據結構之大頂堆，開啟數據結構之路技术頭條網

2020-04-07 14:27:00 C語言基礎

前言

堆排序(Heap Sort)是對簡單選擇排序進行的一種改進，是Floyd和William在1964年共同發明的。簡單選擇排序每次選擇一個數所做中間比較結果沒有保存下來，整個排序分配n-1趟遍歷比較，每次只能確定一個數，這個過程中重複執行了多次比較操作。堆排序的目的就是把一趟比較中的中間結果也保存下來。

大頂堆

堆是具有下列性質的完全二叉樹：每個結點的值都大於或等於其左右孩子結點的值，稱為大根堆(大頂堆)。或者每個結點的值都小於或等於其左右孩子結點的值，稱為小根堆(小頂堆)。（注:用二叉樹的方式分析一段連續內存）。

堆排序（Heap Sort）

將待排序的序列構造成一個大頂堆。此時，整個序列的最大值就是堆頂的根結點。將它移走（其實就是將其與堆數組的末尾元素交換，此時末尾元素就是最大值），然後將剩餘的n-1個序列重新構造成一個堆，這樣就會得到n個元素中的次小值。如此反覆，就能得到一個有序序列了。

對堆中的結點按層進行編號，將這種邏輯結構映射到數組中就是下面這個樣子

堆排序基本思想

a.將無序序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆(向上滲透);

b.將堆頂元素與末尾元素交換，將最大元素"沉"到數組末端(向下滲透);

c.重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與當前末尾元素，反覆執行調整+交換步驟，直到整個序列有序。

C語言描述

<code>#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 11
struct heap
{
\tint sizeHeap;
\tint *memeroy;
};
struct heap* createHeap()
{
\tstruct heap* myHeap = (struct heap*)malloc(sizeof(struct heap));
\tmyHeap->sizeHeap = 0;
\tmyHeap->memeroy = (int *)malloc(sizeof(int)*MAX_SIZE);
\treturn myHeap;
}
//向上滲透調整堆
void moveToCrrectPos(struct heap* myHead, int curPos)
{
\twhile (curPos > 1)
\t{
\t\tint Max = myHead->memeroy[curPos];
\t\tint parentPos = curPos / 2;
\t\tif (Max > myHead->memeroy[parentPos])
\t\t{
\t\t\tmyHead->memeroy[curPos] = myHead->memeroy[parentPos];
\t\t\tmyHead->memeroy[parentPos] = Max;
\t\t\tcurPos = parentPos; 
\t\t}
\t\telse //剛好父節點中的值大於我們插入的值
\t\t{
\t\t\tbreak;
\t\t}
\t}
}

void insert(struct heap* myHeap, int data) 

{
\t++myHeap->sizeHeap;
\t//堆的最後
\tmyHeap->memeroy[myHeap->sizeHeap] = data;
\t//調整堆
\tmoveToCrrectPos(myHeap, myHeap->sizeHeap);
}
int  popMaxHeap(struct heap* myHeap)
{
\tint  Max = myHeap->memeroy[1];
\tint curPos = 1;
\tint childPos = curPos * 2;
\twhile (childPos <= myHeap->sizeHeap)
\t{
\t\t//每一層第一個元素
\t\tint temp = myHeap->memeroy[childPos];
\t\tif (childPos + 1 <= myHeap->sizeHeap&&temp < myHeap->memeroy[childPos + 1])
\t\t{
\t\t\t++childPos;\t//childPos + 1
\t\t\ttemp = myHeap->memeroy[childPos];
\t\t}
\t\tmyHeap->memeroy[curPos] = temp;
\t\tcurPos = childPos;
\t\tchildPos *= 2;
\t}
\tmyHeap->memeroy[curPos] = myHeap->memeroy[myHeap->sizeHeap];
\t--myHeap->sizeHeap;
\treturn Max;
}

int main()
{
\tsrand((unsigned int)time(NULL));
\tstruct heap* myHeap = createHeap();
\tfor (int i = 0; i < 10; i++)
\t{
\t\tinsert(myHeap, rand() %100);
\t}
\tfor (int i = 1; i < 11; i++)
\t{
\t\tprintf("%d\\t", myHeap->memeroy[i]);
\t}
\tprintf("\\n");
\twhile (myHeap->sizeHeap>0)
\t{
\t\tprintf("%d\\t", popMaxHeap(myHeap));
\t}

\tprintf("\\n"); 

\tsystem("pause");
\treturn 0;
}/<time.h>/<stdlib.h>/<stdio.h>/<code>