一香浩、簡介
二叉堆是完全二叉樹或者是近似完全二叉樹类缤。
二叉堆滿足二個特性：
1．父結(jié)點的鍵值總是大于或等于（小于或等于）任何一個子節(jié)點的鍵值
2．每個結(jié)點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）
當父結(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值時為最大堆。當父結(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為最小堆邻吭。
堆排序是一種樹形選擇排序餐弱，是對直接選擇排序的有效改進。
堆的定義下：具有n個元素的序列 （h1,h2,...,hn),當且僅當滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)時稱之為堆囱晴。在這里只討論滿足前者條件的堆膏蚓。由堆的定義可以看出，堆頂元素（即第一個元素）必為最大項（大頂堆）速缆。完全二叉樹可以很直觀地表示堆的結(jié)構(gòu)。堆頂為根恩闻，其它為左子樹艺糜、右子樹。
思想:初始時把要排序的數(shù)的序列看作是一棵順序存儲的二叉樹幢尚，調(diào)整它們的存儲序破停，使之成為一個堆，這時堆的根節(jié)點的數(shù)最大尉剩。然后將根節(jié)點與堆的最后一個節(jié)點交換真慢。然后對前面(n-1)個數(shù)重新調(diào)整使之成為堆。依此類推理茎，直到只有兩個節(jié)點的堆黑界，并對它們作交換，最后得到有n個節(jié)點的有序序列皂林。從算法描述來看朗鸠，堆排序需要兩個過程，一是建立堆础倍，二是堆頂與堆的最后一個元素交換位置烛占。所以堆排序有兩個函數(shù)組成。一是建堆的滲透函數(shù)沟启，二是反復調(diào)用滲透函數(shù)實現(xiàn)排序的函數(shù)忆家。
二、步驟
- 產(chǎn)生初始堆
- 把堆頂?shù)淖畲髷?shù)取出,將剩余的堆繼續(xù)調(diào)整為最大堆,以遞歸實現(xiàn)
- 剩余部分調(diào)整為最大堆后,再次將堆頂?shù)淖畲髷?shù)取出,再將剩余部分調(diào)整為最大堆,這個過程持續(xù)到剩余數(shù)只有一個時結(jié)束
三德迹、示例
初始堆的構(gòu)建
堆排序
四芽卿、代碼實現(xiàn)
1. ShiftUp
// 將元素向上移動(將k位置的元素與父節(jié)點交換位置)
void shiftUp(int k) {
while (k > 1 && data[k / 2] < data[k]) { // data[k/2]是父節(jié)點，data[k]是該元素
swap(data[k / 2], data[k]);
k /= 2; //更新一下k胳搞，以看與新的父節(jié)點之間是否違背了最大堆的定義蹬竖。保證k最多到2沼沈，父節(jié)點k/2就是1
}
}
2. ShiftDown
// 左(j)右(j+1)兩個孩子比較，誰大就和父節(jié)點k交換币厕，向下進行轉(zhuǎn)換
void shiftDown(int k) {
while (2 * k <= count) { // 怎么表示k位置元素有孩子列另？在完全二叉樹中只要有左孩子就表示有孩子了
int j = 2 * k; // 如果沒有右孩子.在此輪循環(huán)中，data[k]和data[j]交換位置
if (j + 1 <= count && data[j + 1] > data[j]) j++; // j + 1 <= count說明有右孩子 并且 右孩子比左孩子大 則j+=1
if (data[k] >= data[j]) break; // 如果父節(jié)點>=兩個孩子就跳出循環(huán)旦装，否則data[k]和data[j]進行交換
swap(data[k], data[j]);
k = j; // 以后繼續(xù)移動k位置的元素
}
}
3. insert
// 向堆中添加一個元素页衙。將新加入的元素放置到合適的位置(與它的父節(jié)點比大小，看是否違背了最大堆的定義)
void insert(Item item) {
assert(count + 1 <= capacity);
data[count + 1] = item;
shiftUp(count + 1);
count++;
}
4. extractMax
// 從堆中取出最大值阴绢，然后count-=1店乐。取出后要把最后一個元素填補到該位置。最后調(diào)整位置保證最大堆定義
Item extractMax() {
assert(count > 0);
Item ret = data[1]; // 取出最大值
swap(data[1], data[count]); // 將最大值元素與最后一個元素交換
count--; // 不考慮count位置的元素了
shiftDown(1); // 將第一個位置的元素向下移到合適的位置以滿足最大堆的定義
return ret;
}
5. 排序函數(shù)1
template<typename T>
void heapSort1(T arr[], int n) {
MaxHeap<T> maxheap = MaxHeap<T>(n);
for (int i = 0; i < n; i++)
maxheap.insert(arr[i]);
for (int i = n - 1; i >= 0; i--) // 反向遍歷呻袭，這樣排序出來是遞增順序
arr[i] = maxheap.extractMax();
}
6. 排序函數(shù)2
template<typename T>
void heapSort2(T arr[], int n){
MaxHeap<T> maxheap = MaxHeap<T>(arr,n); // 已經(jīng)構(gòu)造成了一個堆眨八，更快
for( int i = n-1 ; i >= 0 ; i-- )
arr[i] = maxheap.extractMax();
}
完整代碼
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
template<typename Item>
class MaxHeap {
private:
Item *data;
int count;
int capacity;
// 將元素向上移動(將k位置的元素與父節(jié)點交換位置)
void shiftUp(int k) {
while (k > 1 && data[k / 2] < data[k]) { // data[k/2]是父節(jié)點，data[k]是該元素
swap(data[k / 2], data[k]);
k /= 2; //更新一下k左电，以看與新的父節(jié)點之間是否違背了最大堆的定義廉侧。保證k最多到2，父節(jié)點k/2就是1
}
}
// 左(j)右(j+1)兩個孩子比較篓足，誰大就和父節(jié)點k交換段誊，向下進行轉(zhuǎn)換
void shiftDown(int k) {
while (2 * k <= count) { // 怎么表示k位置元素有孩子？在完全二叉樹中只要有左孩子就表示有孩子了
int j = 2 * k; // 如果沒有右孩子.在此輪循環(huán)中栈拖，data[k]和data[j]交換位置
if (j + 1 <= count && data[j + 1] > data[j]) j++; // j + 1 <= count說明有右孩子 并且 右孩子比左孩子大 則j+=1
if (data[k] >= data[j]) break; // 如果父節(jié)點>=兩個孩子就跳出循環(huán)连舍，否則data[k]和data[j]進行交換
swap(data[k], data[j]);
k = j; // 以后繼續(xù)移動k位置的元素
}
}
public:
// 構(gòu)造函數(shù)
MaxHeap(int capacity) {
data = new Item[capacity + 1];
count = 0;
this->capacity = capacity;
}
MaxHeap(Item arr[], int n) {
data = new Item[n + 1];
capacity = n;
for (int i = 0; i < n; i++)
data[i + 1] = arr[i];
count = n;
for (int i = count / 2; i >= 1; i--)
shiftDown(i);
}
~MaxHeap() {
delete[] data;
}
int size() {
return count;
}
bool isEmpty() {
return count == 0;
}
// 向堆中添加一個元素。將新加入的元素放置到合適的位置(與它的父節(jié)點比大小涩哟，看是否違背了最大堆的定義)
void insert(Item item) {
assert(count + 1 <= capacity);
data[count + 1] = item;
shiftUp(count + 1);
count++;
}
// 從堆中取出最大值索赏，然后count-=1。取出后要把最后一個元素填補到該位置贴彼。最后調(diào)整位置保證最大堆定義
Item extractMax() {
assert(count > 0);
Item ret = data[1]; // 取出最大值
swap(data[1], data[count]); // 將最大值元素與最后一個元素交換
count--; // 不考慮count位置的元素了
shiftDown(1); // 將第一個位置的元素向下移到合適的位置以滿足最大堆的定義
return ret;
}
Item getMax() {
assert(count > 0);
return data[1];
}
};
template<typename T>
void heapSort2(T arr[], int n) {
MaxHeap<T> maxheap = MaxHeap<T>(arr, n);
for (int i = n - 1; i >= 0; i--)
arr[i] = maxheap.extractMax();
}
template<typename T>
void heapSort1(T arr[], int n) {
MaxHeap<T> maxheap = MaxHeap<T>(n);
for (int i = 0; i < n; i++)
maxheap.insert(arr[i]);
for (int i = n - 1; i >= 0; i--)
arr[i] = maxheap.extractMax();
}
template<typename T>
void heapSort(T arr[], int n) {
// 從(最后一個元素的索引-1)/2開始
// 最后一個元素的索引 = n-1
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
__shiftDown2(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
__shiftDown2(arr, i, 0);
}
}
int main()
{
int a[10] = { 3,2,5,21,9,10,7,16,8,20 };
heapSort(a,10);
for (int i = 0; i < 10; i++) {
cout << a[i] << " ";
}
}
五参滴、評價
由于每次重新恢復堆的時間復雜度為O(logN)，共N 1次重新恢復堆操作锻弓，再加上前面建立堆時N/2次向下調(diào)整砾赔，每次調(diào)整時間復雜度也為O(logN)。二次操作時間相加還是O(N logN)青灼。故堆排序的時間復雜度為O(N logN)暴心。
經(jīng)典排序算法 - 堆排序Heap sort
經(jīng)典排序算法系列7----堆與堆排序
選擇排序：堆排序（Heap Sort）
白話經(jīng)典算法系列之七 堆與堆排序
