您好,登錄后才能下訂單哦!
這篇文章主要介紹了C語言堆怎么實(shí)現(xiàn)和堆排序是什么的相關(guān)知識,內(nèi)容詳細(xì)易懂,操作簡單快捷,具有一定借鑒價值,相信大家閱讀完這篇C語言堆怎么實(shí)現(xiàn)和堆排序是什么文章都會有所收獲,下面我們一起來看看吧。
堆的介紹
堆的接口實(shí)現(xiàn)
堆排序
一般來說,堆在物理結(jié)構(gòu)上是連續(xù)的數(shù)組結(jié)構(gòu),在邏輯結(jié)構(gòu)上是一顆完全二叉樹。
但要滿足
每個父親節(jié)點(diǎn)的值都得大于孩子節(jié)點(diǎn)的值,這樣的堆稱為大堆。
每個父親節(jié)點(diǎn)的值都得小于孩子節(jié)點(diǎn)的值,這樣的堆稱為小堆。
那么以下就是一個小堆。
百度百科:
堆的定義如下:n個元素的序列{k1,k2,ki,…,kn}當(dāng)且僅當(dāng)滿足下關(guān)系時,稱之為堆。
若將和此次序列對應(yīng)的一維數(shù)組(即以一維數(shù)組作此序列的存儲結(jié)構(gòu))看成是一個完全二叉樹,則堆的含義表明,完全二叉樹中所有非終端結(jié)點(diǎn)的值均不大于(或不小于)其左、右孩子結(jié)點(diǎn)的值。由此,若序列{k1,k2,…,kn}是堆,則堆頂元素(或完全二叉樹的根)必為序列中n個元素的最小值(或最大值)。
下面序列是堆的是( )。
A.97,56,38,66,23,42,12 //不是大堆也不是小堆,即不是堆。
B.23,86,48,3,35,39,42 //不是大堆也不是小堆,即不是堆。
C.05,56,20,23,40,38,29 //不是大堆也不是小堆,即不是堆。
D.05,23,16,68,94,72,71,73 //是小堆
只有D是堆而且是小堆,因此答案選D。
D的邏輯結(jié)構(gòu):
父親節(jié)點(diǎn)和孩子節(jié)點(diǎn)的數(shù)組下標(biāo)有以下關(guān)系:
left_child=(parent+1)*2
right_child=(parent+2)*2
parent=(child-1)/2(這里的child左孩子和右孩子都適用)
以上就不做證明了,不過我們可以驗(yàn)證一下,以上圖D的邏輯結(jié)構(gòu)為例,16的parent下標(biāo)是2,72的下標(biāo)是5,71的下標(biāo)是6,滿足left_child=(parent+1)*2、right_child=(parent+2)*2、parent=(child-1)/2。
有序一定是堆,堆不一定有序。
同時堆頂?shù)臄?shù)組是整個數(shù)組最大的數(shù)或者整個數(shù)組最小的數(shù)。
第一件事我們就是要創(chuàng)建堆,實(shí)際就是創(chuàng)建一個數(shù)組,這里用動態(tài)數(shù)組。
typedef int HPDataType; typedef struct Heap { HPDataType* a; size_t size; size_t capacity; }HP;
堆創(chuàng)建好之后,我們需要對它進(jìn)行初始化。
第一個接口:
void HeapInit(HP* php);
輕車熟路,將堆中的a置為NULL,size和capacity置為0。
或者這里可以設(shè)置capacity不為0的初始值也是可以的。
參考代碼:
void HeapInit(HP* php) { assert(php); php->a = NULL; php->size = php->capacity = 0; }
我們對堆進(jìn)行初始化之后,也要在最后銷毀堆。
第二個接口:
void HeapDestroy(HP* php)
銷毀堆,即銷毀一個動態(tài)數(shù)組
參考代碼:
void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->size = php->capacity = 0; }
現(xiàn)在我們可以考慮往堆中插入數(shù)據(jù)了,要求插入新元素之后還是堆。
第三個接口:
void HeapPush(HP* php, HPDataType x)
堆沒有要求在哪個位置插入新元素,可以在任意的位置插入新元素,但要保證插入新元素之后還是堆。
由于數(shù)組在頭部還是在中間位置的插入復(fù)雜度是O(N),并且插入后不一定是堆了。
因此我們考慮的是直接在數(shù)組尾部插入新元素,然后用一個函數(shù)去調(diào)整數(shù)組的順序使得它還是一個堆。
那么核心代碼就是這個調(diào)整算法。
先來看這一個堆,插入新元素后該如何進(jìn)行調(diào)整。
我們在數(shù)組的最后插入22,原堆是一個小堆,此時我們需要從下往上去調(diào)整各個父親節(jié)點(diǎn),使得該堆還是一個小堆。
換句話說:我們只需要調(diào)整下面有彩色的節(jié)點(diǎn)順序。
交換過程:如果孩子節(jié)點(diǎn)小于父親節(jié)點(diǎn),那么將它們交換,然后迭代。
如果孩子節(jié)點(diǎn)大于父親節(jié)點(diǎn)就跳出循環(huán)。
迭代過程:將父親節(jié)點(diǎn)的下標(biāo)賦值給孩子節(jié)點(diǎn)的下標(biāo),然后重新計(jì)算父親節(jié)點(diǎn)的下標(biāo),計(jì)算方法:parent=(child-1)/2。
參考代碼:
void AdjustUp(HPDataType* a, size_t child) { size_t parent = (child - 1) / 2; while (child > 0) { //如果孩子小于父親,則交換 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } //孩子大于父親,則結(jié)束調(diào)整 else { break; } } }
void HeapPush(HP* php, HPDataType x) { assert(php); //動態(tài)數(shù)組,空間不夠要擴(kuò)容 if (php->size == php->capacity) { size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2; HPDataType* tmp = realloc(php->a, sizeof(HPDataType)* newCapacity); if (tmp == NULL) { printf("realloc failed\n"); exit(-1); } php->a = tmp; php->capacity = newCapacity; } //尾插數(shù)據(jù) php->a[php->size] = x; ++php->size; // 向上調(diào)整,控制保持是一個小堆 AdjustUp(php->a, php->size - 1); }
上面是多個數(shù)據(jù)的插入,那么如果插入第一個數(shù)據(jù),這個函數(shù)還能幫助我們把數(shù)據(jù)插入堆中嗎?
答案是肯定的。
既然有Push數(shù)據(jù)到堆,自然有從堆中刪除元素了。
這里的刪除不同于棧和隊(duì)列的刪除,這里指的是將堆頂?shù)臄?shù)據(jù)刪除,刪除之后堆還是一個堆。為什么只實(shí)現(xiàn)刪堆頂?shù)臄?shù)據(jù),因?yàn)楹唵螌?shí)用,這個接口是為后面的堆排序做準(zhǔn)備的。
第四個接口:
void HeapPop(HP* php)
思路比較簡單:將數(shù)組第一個元素刪除,然后保持它還是一個小堆。
怎么刪除第一個數(shù)據(jù)呢?
這里的考慮是將數(shù)組第一個元素和數(shù)組最后一個交換,交換之后尾刪掉最后一個元素,達(dá)成刪除第一個元素的效果,復(fù)雜度是O(N),這里可以提一下,這種頭刪的方式是改變了數(shù)組元素的相對順序的。
刪除之后我們要做調(diào)整,使得堆還是小堆。
那么怎么調(diào)整呢?
以下是一個小堆
頭刪之后
如何調(diào)整它,使得它還是一個小堆?
這里的思路是:向下調(diào)整算法,首先parent=73,然后選出它子節(jié)點(diǎn)最小的值,然后它們之間交換,交換之后,將子節(jié)點(diǎn)看作新的父親節(jié)點(diǎn),繼續(xù)向下調(diào)整,直到父親節(jié)點(diǎn)的左孩子不存在。
參考代碼:
void AdjustDown(HPDataType* a, size_t size, size_t root) { size_t parent = root; size_t child = parent * 2 + 1; while (child < size) { // 1、選出左右孩子中小的那個 if (child + 1 < size && a[child+1] < a[child]) { ++child; } // 2、如果孩子小于父親,則交換,并繼續(xù)往下調(diào)整 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
這里需要注意的是,為什么循環(huán)的結(jié)束條件不是右孩子不存在呢?
因?yàn)橛液⒆硬淮嬖跁r,也可能要進(jìn)行交換。
比如:
還需要注意的是左孩子存在右孩子不一定存在
if (a[child+1] > a[child]) { ++child; }
直接這樣寫a[child+1]可能會越界,因此要加上child + 1 < size,保證child + 1 <= size-1。
參考代碼:
void HeapPop(HP* php) { assert(php); assert(php->size > 0); //將數(shù)組第一個元素和最后一個元素交換然后刪除最后一個元素,達(dá)到頭刪的目的。 Swap(&php->a[0], &php->a[php->size - 1]); --php->size; //向下調(diào)整算法 AdjustDown(php->a, php->size, 0); }
其他接口補(bǔ)充:
由于比較簡單,理解起來不費(fèi)勁,因此這里直接給出。
參考代碼:
bool HeapEmpty(HP* php)//判斷堆是否為空 { assert(php); return php->size == 0; } size_t HeapSize(HP* php)//堆的元素個數(shù) { assert(php); return php->size; } HPDataType HeapTop(HP* php)//取堆頂數(shù)據(jù) { assert(php); assert(php->size > 0); return php->a[0]; }
堆排序:利用堆頂節(jié)點(diǎn)是整個數(shù)組的最大值或者最小值的特點(diǎn),可以達(dá)到排序的目的。
比如我們要將1、5、2、4、8、6、10排成升序
可以將這幾個元素依次入堆,使得這些數(shù)據(jù)變成小堆。
然后我們可以取堆的第一個元素,它是整個數(shù)組最小的元素,要排升序,那么我們就需要將它排在第一個位置,然后刪除堆頂元素,由于我們的刪除接口的作用是:刪除堆頂元素,并保持堆還是小堆,那么我們調(diào)用刪除接口之后,再取堆頂元素,將它排在第二個位置,依次繼續(xù)下去,我們就能將這些數(shù)據(jù)排成升序了。
參考代碼:
void HeapSort(int* a, int size) { HP hp; HeapInit(&hp); //建小堆 for (int i = 0; i < size; ++i) { HeapPush(&hp, a[i]); } //不斷取堆頂元素進(jìn)行排序 size_t j = 0; while (!HeapEmpty(&hp)) { a[j] = HeapTop(&hp); j++; HeapPop(&hp); } //銷毀堆,防止內(nèi)存泄露 HeapDestroy(&hp); }
這里的堆排序的空間復(fù)雜度是O(N),因?yàn)樵诙褏^(qū)開辟了一個N個元素大小的堆空間。
堆排序看起來挺復(fù)雜的,那么它的時間復(fù)雜度是什么呢?
建小堆:0(N)
HeapPop()一次執(zhí)行的是:頭刪堆頂元素(O(1)),然后依次向下比較,比較的次數(shù)是高度次,因?yàn)槭峭耆鏄洌容^的時間復(fù)雜度是O(logN)。
因此執(zhí)行一次HeapPop的時間復(fù)雜度是O(logN)。
那么不斷取堆頂元素進(jìn)行排序,取了N個元素,調(diào)用了N次HeapPop(),時間復(fù)雜度是O(N*logN)。
總的時間復(fù)雜度是O(N)+O(N*logN),當(dāng)N很大時,加的O(N)可以忽略。
實(shí)際時間復(fù)雜就是:O(N*logN)
空間復(fù)雜度:O(N)
那么堆排序的時間復(fù)雜度是O(N*logN)。
相比于冒泡排序的O(N*N)。
堆排序顯然效率更高。
如果N等于100萬,冒泡要執(zhí)行1萬億次,而堆排序執(zhí)行2千萬次,效率可想而知!
關(guān)于“C語言堆怎么實(shí)現(xiàn)和堆排序是什么”這篇文章的內(nèi)容就介紹到這里,感謝各位的閱讀!相信大家對“C語言堆怎么實(shí)現(xiàn)和堆排序是什么”知識都有一定的了解,大家如果還想學(xué)習(xí)更多知識,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。