一、简介
二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性：
1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值
2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义下：具有n个元素的序列 （h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
二、步骤
- 产生初始堆
- 把堆顶的最大数取出,将剩余的堆继续调整为最大堆,以递归实现
- 剩余部分调整为最大堆后,再次将堆顶的最大数取出,再将剩余部分调整为最大堆,这个过程持续到剩余数只有一个时结束
三、示例
初始堆的构建
堆排序
四、代码实现
1. ShiftUp
// 将元素向上移动(将k位置的元素与父节点交换位置)
void shiftUp(int k) {
while (k > 1 && data[k / 2] < data[k]) { // data[k/2]是父节点，data[k]是该元素
swap(data[k / 2], data[k]);
k /= 2; //更新一下k，以看与新的父节点之间是否违背了最大堆的定义。保证k最多到2，父节点k/2就是1
}
}
2. ShiftDown
// 左(j)右(j+1)两个孩子比较，谁大就和父节点k交换，向下进行转换
void shiftDown(int k) {
while (2 * k <= count) { // 怎么表示k位置元素有孩子？在完全二叉树中只要有左孩子就表示有孩子了
int j = 2 * k; // 如果没有右孩子.在此轮循环中，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; // 如果父节点>=两个孩子就跳出循环，否则data[k]和data[j]进行交换
swap(data[k], data[j]);
k = j; // 以后继续移动k位置的元素
}
}
3. insert
// 向堆中添加一个元素。将新加入的元素放置到合适的位置(与它的父节点比大小，看是否违背了最大堆的定义)
void insert(Item item) {
assert(count + 1 <= capacity);
data[count + 1] = item;
shiftUp(count + 1);
count++;
}
4. extractMax
// 从堆中取出最大值，然后count-=1。取出后要把最后一个元素填补到该位置。最后调整位置保证最大堆定义
Item extractMax() {
assert(count > 0);
Item ret = data[1]; // 取出最大值
swap(data[1], data[count]); // 将最大值元素与最后一个元素交换
count--; // 不考虑count位置的元素了
shiftDown(1); // 将第一个位置的元素向下移到合适的位置以满足最大堆的定义
return ret;
}
5. 排序函数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. 排序函数2
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();
}
完整代码
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
template<typename Item>
class MaxHeap {
private:
Item *data;
int count;
int capacity;
// 将元素向上移动(将k位置的元素与父节点交换位置)
void shiftUp(int k) {
while (k > 1 && data[k / 2] < data[k]) { // data[k/2]是父节点，data[k]是该元素
swap(data[k / 2], data[k]);
k /= 2; //更新一下k，以看与新的父节点之间是否违背了最大堆的定义。保证k最多到2，父节点k/2就是1
}
}
// 左(j)右(j+1)两个孩子比较，谁大就和父节点k交换，向下进行转换
void shiftDown(int k) {
while (2 * k <= count) { // 怎么表示k位置元素有孩子？在完全二叉树中只要有左孩子就表示有孩子了
int j = 2 * k; // 如果没有右孩子.在此轮循环中，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; // 如果父节点>=两个孩子就跳出循环，否则data[k]和data[j]进行交换
swap(data[k], data[j]);
k = j; // 以后继续移动k位置的元素
}
}
public:
// 构造函数
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;
}
// 向堆中添加一个元素。将新加入的元素放置到合适的位置(与它的父节点比大小，看是否违背了最大堆的定义)
void insert(Item item) {
assert(count + 1 <= capacity);
data[count + 1] = item;
shiftUp(count + 1);
count++;
}
// 从堆中取出最大值，然后count-=1。取出后要把最后一个元素填补到该位置。最后调整位置保证最大堆定义
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次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N logN)。故堆排序的时间复杂度为O(N logN)。
经典排序算法 - 堆排序Heap sort
经典排序算法系列7----堆与堆排序
选择排序：堆排序（Heap Sort）
白话经典算法系列之七 堆与堆排序
