1.堆的概念
堆通常是一個可以被看做一棵完全二叉樹，
（1）大根堆， 就是說這個完全二叉樹中每一棵子樹的根節點都大于他的左右孩子（如果有的話），
（2）小根堆，就是說這個完全二叉樹中每一棵子樹的根節點都小于他的左右孩子（如果有的話），
在陣列中：
如果父節點的下標為i，則左孩子的下標為 2 * i + 1，右孩子下標為2*i+2，
如果孩子的下標為j， 則父節點的下標是：（ j - 1 ） / 2，
2.堆的調整建立程序
將陣列中的資料調整成堆時，從最后一棵子樹開始，向根節點一顆顆調整，每棵子樹的調整都是從其根節點開始向下調整的，
先用i指向子樹的根節點，j為根節點的左孩子，將i位置的值保存到tmp中， 然后在左右孩子中找到較大的哪一個，j指向較大值，（1）如果較大的哪一個比臨時變數中的值小，則直接退出；（2）如果較大的哪一個比臨時變數中的值大，則將較大的值保存到i位置上，然后i=j，j=2*i+1，直到j越界則退出，退出以后，還需要將tmp的值保存到退出時的i位置上，
我們以陣列7，3，2，4，3，11，57，23，1，3，4為例
它們根據下標對應的樹形關系如下：
調整是以底向上的調整，第一次調整就是最后一顆子樹，如下紅圈即最后一棵子樹，以下標集合表示，{4，9，10}即最后一顆子樹
調整后變成如下的一顆樹，{3，7，8}是倒數第二顆子樹，對其進行調整，使得根（下標3）值最大
調整后變成如下一棵樹，{2，5，6}即我們要調整的下一顆樹，使得這顆子樹的最大值放在根上（即下標2上），
調整后如下樹，
下一顆要調整的樹是{1，3，4，7，8，9，10}，在這里要注意一下，我們需要對每一顆子樹的所有根進行調整，即先調整下標為1的這個根，然后調整下標為3或者4的其中一個根，比如這棵子樹，i是下標1，j是下標為3和4中的值較大的一個下標，在這里j就是下標3，由于sum[i] < sum[j]所以將下標i和j的值交換，變成如下圖的樹：
由于子樹{3，7，8}根值變動了，所以我們需要對子樹{3，7，8}再次進行調整，調整后如下圖：
然后再對樹{0，1，2，3，4，5，6，7，8，9，10}進行調整，和上次調整一樣，在這里我們需要讓下標0，1，2中最大值放在0下標即被調整的樹的根的位置，在這里我們就把57（下標2）和7（下標0）交換了，
然后再對樹{2，5，6}進行調整，直至調整到最后一個根節點，調整完后的樹為：
注意這棵樹是我們進行兩次交換后的結果，即下標0和下標2，下標2和下標5，如果下標5是個根節點的話（即下標5有子節點），那么我們需要對以下標5為根節點的樹繼續進行調整，直至調整到葉子節點或者子樹已經是大根堆為止，
下面代碼是對一棵樹的調整代碼（注意被調整前的樹的左右兩顆子樹肯定是大根堆），那么怎么保證被調整的樹的子樹是大根堆呢？我們只需要從一顆大樹的最后一個根節點一個一個根節點向root結點開始調整就可以，就是我們上面的調整程序，
#include<iostream>
#include<assert.h>
using namespace std;
void OneAdjust(int* arr, int len, int root)
{
int i = root;
int j = 2 * i + 1;
while (j < len)
{
if (j + 1 < len && arr[j] < arr[j + 1])//讓j是左右子結點值較大的下標
{
j = j + 1;
}
if (arr[i] >= arr[j])//說明需要調整的樹的根節點比左右子節點都大，左右子樹都是大根堆，所以這棵樹也是大根堆
{
break;
}
else//
{
swap(arr[i], arr[j]);
i = j;//調整改動的子樹
j = 2 * i + 1;
}
}
}
我們需要從最后一個根，慢慢向上面的根調整，所以整棵樹的調整代碼如下：
void CreateHeap(int* arr,int len)
{
int lastroot = (len - 1 - 1) / 2;//找最后一棵子樹的根節點下標，len-1是最后一個節點的下標，再-1然后除以2就是最后一個根
for (int i = lastroot; i >= 0; i--)//從lastroot，向上一個根一個根的調整
{
OneAdjust(arr, len, i);
}
}
3.堆排
先將陣列中的資料調整成一棵最大堆， 然后將根節點的資料和最后位置的節點交換（即調整一次，將大根堆的根放在最后）， 接著除過最后一個位置的資料外，在將剩余的資料調整成最大堆，
重復上述程序，直到只剩下一個資料沒有交換，就完成了堆排序，
// 時間復雜度： O(nlog(n))
// 空間復雜度： O(1)
// 穩定性： 不穩定
void HeapSort(int* arr, int len)
{
CreateHeap(arr, len);
for (int i = 0; i < len - 1; i++)
{
swap(arr[0], arr[len - 1 - i]);//將大根堆的根值放在待排序資料的最后位置
OneAdjust(arr, len-1-i, 0);//只需要對剩下的資料進行一次調整，對根進行調整
}
}
int main()
{
int arr[] = { 1,3,4,7,8,23,51,67,3,0 };
HeapSort(arr, 10);
for (int i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
運行結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/304580.html
標籤：其他
上一篇：購物車案例