排序算法3=堆排序+二叉堆

一、什么是二叉堆
堆是一种存储数据的结构，形状类似于金字塔形，所以形象的称之为堆结构。
二叉堆：是指一种将二叉树和堆结合起来的数据结构，这种数据结构有两个主要的特点，其一是满足完全二叉树的性质，顺序存储，中间不存在空余位置，其二是任意一个结点的父节点大于（或小于）子结点。
其中堆的存储方式是采用数组进行存储，所以堆通常可以被看做是一个完全二叉树的数组对象。
其中根结点最大的称为最大堆，根结点最小的称为最小堆。
二、怎么用代码定义一个二叉堆

#include<iostream>
#include<string>
#include<ctime>
using namespace std;
template<typename T>
class maxHeap {
private:
    int size;
    T* arr;
    void shiftUp(int size) {
        while (size >= 2) {
            if (arr[size] > arr[size / 2]) {
                swap(arr[size], arr[size / 2]);
                size /= 2;
            }
            else
                break;    
        }
    }
    void shiftDown(int k) {
        while (2 * k <= size) {
            int j = 2 * k;;
            if (j+ 1 <= size && arr[j] < arr[j+1])
                j += 1;
            if (arr[k] >= arr[j])
                break;
            swap(arr[k], arr[j]);
            k = j;
        }
    }
public:
    maxHeap(int n) {
        arr = new T[n+1];
        size = 0;
    }
    ~maxHeap() {
        delete[] arr;
    }
    int Size() {
        return size;
    }
    bool isEmpty() {
        return size == 0;
    }
    void insert(T k) {
        arr[size + 1] = k;
        size++;
        shiftUp(size);
    }
    void print() {
        for (int i = 1; i <=size; i++)
            cout << arr[i]<<" ";
        cout << endl;
    }
    T extractTop() {
        T temp = arr[1];
        arr[1] = arr[size];
        size--;
        shiftDown(1);
        return temp;
    }

};
int main() {
    int n = 10;
    maxHeap<int> maxheap = maxHeap<int>(n);
    srand((unsigned int)time(NULL));
    for (int i = 0; i < n; i++)
        maxheap.insert(rand() % 100 + 1);
    cout << "原排列：" << endl;
    maxheap.print();
    cout << "从大到小排序：" << endl;
    for (int i = 0; i < n; i++) {
        cout << maxheap.extractTop() << "  ";
    }
    cout << endl;
    system("pause");
    return 0;
}

接下来，我简单讲解一下代码组成。
第一部分是堆的基本定义，用模板类的形式定义了一个最大堆，其中包括私有成员arr数组，size为成员个数，注意的是本次代码用数组存储堆时是从序号1开始存储，定义公有成员有参构造函数，传入参数开辟数组内存空间大小同时size初始化为0，析构函数删除堆，同时还定义了两个成员函数，返回堆成员的个数和判断是否为空。然后在主函数内创建对象，传入内存空间大小。
第二部分，进行堆的插入，这里用图来形象说明一下。图中已经有了10个元素，从上到下，从左至右序号分别是1，2，3，4，5，6，7，8，9，10，假设现在要插入一个数序号为11，值为80，初始时80位于序号为5的右子树，然后开始逐级往上比，循环条件是序列号大于等于2，因为根结点的序号为1，等于2时进行的就是最后一次比较。序号11值80比序号11/2值45大，则交换这两个元素在数组中的位置，同时把值80的序号变成11/2=5，然后序号5值80比序号5/2=2值72大，则交换这两个元素在数组中的位置，同时把值80的序号变成5/2=2，然后序号2值80比序号2/2=1值93小跳出循环，循环结束，最大堆完成。
图片说明
第三部分，进行堆排序，由于最大堆的特点根结点时最大的值，所以只要每次取出根结点的值，然后把剩下的堆再次变成最大堆的形式，则就可以逐次取出最大值，输出也就是从大到小的一个排序序列了。
这里以上面最后一个排好的最大堆为例，令temp=93，然后把45赋值到序列1的位置上，同时size--，进入重组最大堆的函数中，传入序号1，循环条件是该节点存在子节点即2i<=size的，然后定义小标j=2i；判断是否存在j+1，即是否存在右子树且右子树是否大于左子树，如果满足则j=j+1；然后将该小标对应的元素值与父节点进行比较，如果子结点大于父节点则交换这两个数的位置，同时i=j进行赋值进行下一层的比较，如果子节点不大于父节点则跳出循环。此时循环结束后又恢复成了最大堆的形式。