C語言數(shù)據(jù)結構中堆排序的分析總結
一、本章重點
- 堆
- 向上調整
- 向下調整
- 堆排序
二、堆
2.1堆的介紹（三點）
1.物理結構是數(shù)組
2.邏輯結構是完全二叉樹
3.大堆:所有的父親節(jié)點都大于等于孩子節(jié)點，小堆：所有的父親節(jié)點都小于等于孩子節(jié)點。
2.2向上調整
概念：有一個小/大堆，在數(shù)組最后插入一個元素，通過向上調整，使得該堆還是小/大堆。
使用條件：數(shù)組前n-1個元素構成一個堆。
以大堆為例：
邏輯實現(xiàn)：
將新插入的最后一個元素看做孩子，讓它與父親相比，如果孩子大于父親，則將它們交換，將父親看做孩子，在依次比較，直到孩子等于0結束調整·。
如果中途孩子小于父親，則跳出循環(huán)，結束調整。
參考代碼：
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;
}
}
}向上調整應用
給大\小堆加入新的元素之后仍使得大\小堆還是大\小堆。
2.3向下調整
概念：根節(jié)點的左右子樹都是大\小堆，通過向下調整，使得整個完全二叉樹都是大\小堆。
使用條件：根節(jié)點的左右子樹都是大\小堆。
如圖根為23，它的左右子樹都是大堆，但整顆完全二叉樹不是堆，通過向下調整可以使得整顆完全二叉樹是堆。
邏輯實現(xiàn)：
選出根的左右孩子較大的那個孩子，然后與根比較，如果比根大，則交換，否則結束調整。
參考代碼：
void AdjustDown(HPDataType* a, int size, int root)
{
int parent = root;
int child = parent * 2 + 1;//左孩子
while (child < size)
{
if (child + 1 < size && a[child] < a[child + 1])//如果左孩子小于右孩子，則選右孩子
{
//務必加上child+1，因為當child=size-1時，右孩子下標是size，對其接引用會越界訪問。
child++;//右孩子的下標等于左孩子+1
}
if (a[child] > a[parent])//讓較大的孩子與父親比較，如果孩子大于父親，則將它們交換。
{
Swap(&a[child], &a[parent]);
//迭代過程
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}2.4建堆（兩種方式）
第一種：向上調整建堆（時間復雜度是O（N*logN），空間復雜度O（1））
思路是：從第二個數(shù)組元素開始到最后一個數(shù)組元素依次進行向上調整。
參考代碼：
for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}時間復雜度計算：
以滿二叉樹進行計算
最壞情況執(zhí)行步數(shù)為：T=(2^1)*1+(2^2)*2+(2^3)*3+....+2^(h-1)*(h-1)
最后化簡得：T=2^h*(h-2)+2
又因為(2^h)-1=N
所以h=log(N+1)
帶入后得T=(N+1)*(logN-1)+2
因此它的時間復雜度是：O（N*logN）
第二種：向下調整建堆（時間復雜度是O（N），空間復雜度是O（1））
從最后一個非葉子節(jié)點（最后一個數(shù)組元素的父親）開始到第一個數(shù)組元素依次進行向下調整。
參考代碼：
//n代表數(shù)組元素個數(shù)，j的初始值代表最后一個元素的父親下標
for (int j = (n - 1 - 1) / 2; j >= 0; j--)
{
AdjustDown(a, n, j);
}
時間復雜度計算：
以滿二叉樹進行計算
最壞執(zhí)行次數(shù)：
T=2^(h-2)*1+2^(h-3)*2+2^(h-4)*3+.....+2^3*(h-4)+2^2*(h-3)+2^1*(h-2)+2^0*(h-1)
聯(lián)立2^h-1=N
化簡得T=N-log（N+1）
當N很大時，log（N+1）可以忽略。
因此它的時間復雜度是O（N）。
因此我們一般建堆采用向下調整的建堆方式。
三、堆排序
目前最好的排序算法時間復雜度是O（N*logN）
堆排序的時間復雜度是O（N*logN）
堆排序是對堆進行排序，因此當我們對某個數(shù)組進行排序時，我們要先將這個數(shù)組建成堆，然后進行排序。
首先需要知道的是：
對數(shù)組升序，需要將數(shù)組建成大堆。
對數(shù)組降序，需要將數(shù)組建成小堆。
這是為什么呢？
這需要明白大堆和小堆的區(qū)別，大堆堆頂是最大數(shù)，小堆堆頂是最小數(shù)。
當我們首次建堆時，建大堆能夠得到第一個最大數(shù)，然后可以將它與數(shù)組最后的元素進行交換，下一次我們只需要將堆頂?shù)臄?shù)再次進行向下調整，可以再次將數(shù)組變成大堆，然后與數(shù)組的倒數(shù)第二個元素進行交換，自此已經(jīng)排好了兩個元素，使得它們存儲在需要的地方，然后依次進行取數(shù)，調整。
而如果是小堆，首次建堆時，我們能夠得到最小的數(shù)，然后將它放在數(shù)組第一個位置，然后你要保持它還是小堆，該怎么辦呢？只能從第二個元素開始從下建堆，而建堆的時間復雜度是O（N），你需要不斷重建堆，最終堆排序的時間復雜度是O（N*N），這是不明智的。
或者建好小堆后，你這樣做:
在開一個n個數(shù)組的空間，選出第一個最小數(shù)就將它放在新開辟的數(shù)組空間中保存，然后刪除堆頂數(shù)，再通過向下調整堆頂?shù)臄?shù)，再將新堆頂數(shù)放在新數(shù)組的第二個位置.......。
雖然這樣的時間復雜度是O（N*logN）。
但這樣的空間復雜度是O（N）。
也不是最優(yōu)的堆排序方法。
而建大堆的好處就在它把選出的數(shù)放在最后，這樣我們就可以對堆頂進行向下調整，使得它還是大堆，而向下調整的時間復雜度是O(logN)，最終堆排序的時間復雜度是O（N*logN）。
堆排序的核心要義：
通過建大堆或者小堆的方式，選出堆中最大或者最小的數(shù)，從后往前放。
參考代碼：
int end = n - 1;//n代表數(shù)組元素的個數(shù)
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}整個堆排序的代碼：
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void AdjustUp(int* 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 AdjustDown(int* a, int n, int root)
{
int child = 2 * root + 1;
while (child < n)
{
if (child + 1 < n && a[child] < a[child+1])
{
child++;
}
if (a[child] > a[root])
{
Swap(&a[child], &a[root]);
root = child;
child = 2 * root + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
//建大堆(向上調整)
//for (int i = 1; i < n; i++)
//{
// AdjustUp(a, i);
//}
//建大堆(向下調整)
for (int j = (n - 1 - 1) / 2; j >= 0; j--)
{
AdjustDown(a, n, j);
}
//升序
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
void printarr(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main()
{
int arr[10] = { 9,2,4,8,6,3,5,1,10 };
int size = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, size);
printarr(arr, size);
return 0;
}到此這篇關于C語言數(shù)據(jù)結構中堆排序的分析總結的文章就介紹到這了,更多相關C語言 堆排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
結構體是一種工具，用這個工具可以定義自己的數(shù)據(jù)類型。下面通過本文給大家分享了C語言結構體定義的方法匯總，需要的朋友參考下吧2017-12-12
這篇文章主要介紹了C++中CSTRINGLIST用法詳解的相關資料,需要的朋友可以參考下2015-06-06
Ubuntu中使用VS Code與安裝C/C++插件的教程詳解
這篇文章主要介紹了Ubuntu中使用VS Code與安裝C/C++插件的教程詳解,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-09-09
C++軟件開發(fā)可以理解為設計一系列的類，讓這些類相互使用，最終實現(xiàn)我們所需要的功能。類與類之間的相互關系可以很復雜，也可以很簡單，如何簡單高效的描述類與類之間的關系是設計的難點之一。遵循本文所提供的方法，將會給你一些靈感2022-09-09
這篇文章主要介紹了C++的內存分配方式以及介紹了下棧和堆的區(qū)別，感興趣的小伙伴可以參考閱讀本文2023-03-03
這篇文章主要內容是6個默認成員函數(shù)之一的拷貝構造函數(shù)的認識與學習，讓同學們充分理解淺拷貝與深拷貝，感興趣的小伙伴可以參考閱讀2023-04-04
Visual Studio C++指針靠前靠后的問題全面解析
這篇文章主要介紹了Visual Studio C++指針靠前靠后的問題全面解析,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
這篇文章主要介紹了C++?STL中一些常見算法的使用,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-12-12
bind是一組用于函數(shù)綁定的模板。在對某個函數(shù)進行綁定時，可以指定部分參數(shù)或全部參數(shù)，也可以不指定任何參數(shù)，還可以調整各個參數(shù)間的順序。這篇文章主要介紹了c/c++ 標準庫 bind 函數(shù) ,需要的朋友可以參考下2018-09-09
這篇文章主要為大家詳細介紹了C語言實現(xiàn)掃雷游戲及其優(yōu)化，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-08-08