堆

堆 Heap 这种数据结构其实就是一颗 “完全二叉树”，每个节点的值总是不大于或不小于其父节点的值：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。一棵深度为k且有个结点的二叉树称为 “满二叉树”。

堆的分类：

大顶堆：每个节点的值都大于或等于其子节点的值
小顶堆：每个节点的值都小于或等于其子节点的值

大顶堆和小顶堆都可以用来“从小到大”或“从大到小”排序，一般使用大顶堆。

堆的代码实现

堆就是一颗完全二叉树，中间没有空洞，因此可以使用内存连续的数组或动态数组来实现。以大顶堆为例。

先将堆中结点的序号和数组索引进行对应：（与层次遍历类似）

显然，每对父子结点在数组中的索引存在数学关系：

索引为 $t$ 的结点，其父结点索引为 $(t - 1) / 2$
索引为 $t$ 的结点，其左孩子索引为 $t \times 2 + 1$ ，右孩子索引为 $t \times 2 + 2$

插入操作：push

先将元素插入到最后一个结点
由此逐层向上渗透：若比父结点大，就交换

删除操作：pop

先将根节点删除，替换为最后一个结点
由此逐层向下渗透：若比左右结点小，就和bigger交换

模板类代码：

#pragma once
#include <vector>

template<typename T>
class MaxHeap
{
public:
    MaxHeap() {}
    ~MaxHeap() {}
    void push(T& x);
    void pop();
    bool empty() const;
    const T& top() const;

//private:
    std::vector<T> heap;
};

template<typename T>
inline void MaxHeap<T>::push(T& x)
{
    // 添加元素
    heap.push_back(x);
    // 向上渗透
    int index = heap.size() - 1;
    while (index > 0)
    {
        int parent = (index - 1) / 2;
        if (heap[parent] >= x) break;
        heap[index] = heap[parent];
        index = parent;
    }
    heap[index] = x;
}

template<typename T>
inline void MaxHeap<T>::pop()
{
    // 替换根结点
    T x = heap[0] = heap[heap.size() - 1];
    heap.pop_back();
    if (heap.empty()) return;
    // 向下渗透
    int index = 0;
    while (index * 2 + 1 < heap.size()) // 左子结点存在
    {
        int larger_child;
        int l_child = index * 2 + 1;
        int r_child = index * 2 + 2;
        if (r_child < heap.size() && heap[r_child] >= heap[l_child])  // 右子结点存在
        {
            larger_child = r_child;
        }
        else
        {
            larger_child = l_child;
        }
        if (x > heap[larger_child])   // 截止
            break;
        heap[index] = heap[larger_child];
        index = larger_child;
    }
    heap[index] = x;
}

template<typename T>
inline bool MaxHeap<T>::empty() const
{
    return heap.empty();
}

template<typename T>
inline const T& MaxHeap<T>::top() const
{
    return heap[0];
}

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏、最好、平均时间复杂度均为O(nlogn)，是不稳定排序。

基本思想：

构造一个空的大顶堆；
将待排序序列push进入大顶堆，此时，整个序列的最大值就是堆顶的根节点
将大顶堆的根节点反复读出、删除即得到有序序列

堆排序测试代码：

#include <iostream>
#include "MaxHeap.h"

using namespace std;

int main(int argc, char* argv[])
{
    int a[10] = { 11,3,25,177,299,0,52,74,86,308 };
    int n = 10;

    MaxHeap<int> heap;
    for (auto x : a)
    {
        heap.push(x);
    }

    cout << "从小到大：";
    for (int i = n-1; i >=0; i--)
    {
        a[i] = heap.top();
        heap.pop();
    }

    //cout << "从大到小：";
    //for (int i = 0; i < n; i++)
    //{
    // a[i] = heap.top();
    // heap.pop();
    //}

	// 输出排序结果
    for (int i = 0; i < n; i++)
        cout << a[i] << ", ";
    cout << endl;

    return 0;
}

C++11 中的堆 priority_queue

优先队列是一种容器适配器，默认第一个元素总是保持最大，内部类似于堆结构。提供常数时间的最大元素（默认）查找，对数代价的插入与删除(二分法)。

成员函数：

top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列(并排序)
pop 弹出队头元素
swap 交换内容

定义：
priority_queue<Type, Container, Functional>

Type 就是数据类型
Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）
Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入

这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。

小顶堆定义：
priority_queue < int, vector<int>, greater<int> > q;

Data Structures in C++：堆和堆排序

文章目录

堆

堆的代码实现

堆排序

C++11 中的堆 priority_queue