---

數(shù)據(jù)結(jié)構(gòu)----------實現(xiàn)最小堆排序

原理： 來源于---------------趣學(xué)數(shù)據(jù)結(jié)構(gòu) 代碼：

---

#include<stdio.h> #include<stdlib.h> #define N 65535//最大個數(shù)排序 int r[N] = { -1,1,4,590,4,2,8,7,5,89,67,5,2,1,67,86,54 };//存儲要排序的數(shù),第一個元素不存儲元素賦值為-1 void swap(int i, int j) {//交換二個變量的值int temp = r[i];r[i] = r[j];r[j] = temp; } void sink(int k, int n,int flag) {//flag=0表示最大堆，否則最小堆,實現(xiàn)最大（小）堆,即所有根節(jié)點的值大于等于（小于等于）該根節(jié)點下的左右節(jié)點int j = 0;while (2 * k <= n) {//從倒數(shù)第二層有左孩子的結(jié)點開始往上檢查是否滿足每個子樹是否滿足最大（小）堆的條件j = 2 * k;if (flag == 0) {//最大堆的更新條件if (j<n&&r[j + 1]>r[j])j++;//找到當(dāng)前根節(jié)點下最大的值if (r[k] < r[j])swap(k, j);else//該根節(jié)點下已經(jīng)滿足最大堆的條件則退出檢查break;}else {//最小堆的更新條件if (j<n&&r[j + 1]<r[j])j++;//找到當(dāng)前根節(jié)點下最小的值if (r[k] > r[j])swap(k, j);else//該根節(jié)點下已經(jīng)滿足最小堆的條件則退出檢查break;}k = j;//更新了當(dāng)前根結(jié)點的值則繼續(xù)向下檢查是否滿足最大（小）堆的條件 } } void heapSort(int n,int flag) {//最大堆或最小堆排序,flag=0表示最大堆排序，否則最小堆排序，這里的最小堆因為沒有開辟新的空間所以是逆序的，而最大堆的排序結(jié)果是升序的//初始化堆for (int i = n / 2; i > 0; i--) {sink(i, n,flag);}while (n > 1) {swap(1, n);//當(dāng)前第n個元素為第n大(小）元素n--;//選出了最大（小）的元素，則少一個元素sink(1, n, flag);//只改變了根節(jié)點的值，只需要對第一個結(jié)點進行下沉的更新} } void print() {for (int i = 1; r[i] != 0; i++) {printf("%d ", r[i]);} } int main() {printf("初始的順序\n--------------\n");print();printf("\n最小堆排序后結(jié)果\n--------------\n");heapSort(17, 1);print();printf("\n--------------\n");system("pause");return 0; }

---

測試：

---

如果存在什么問題歡迎提出指正！謝謝！

總結(jié)

以上是生活随笔為你收集整理的数据结构----------实现最小堆排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。