堆定义

堆 heap是一种满足特定条件的完全二叉树，主要可分为两种类型，大顶堆和小顶堆

许多编程语言提供的是「优先队列 priority queue」，这是一种抽象的数据结构，定义为具有优先级排序的队列。

实际上，堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看，我们可以将“优先队列”和“堆”看作等价的数据结构。

简单使用

/** * @file heap.cpp * @author your name (you@domain.com) * @brief  * @version 0.1 * @date 2024-02-02 *  * @copyright Copyright (c) 2024 *  */#include "../utils/common.hpp"#include <functional>#include <iostream>#include <queue>#include <vector>void testPush(priority_queue<int> &heap,int val) {    heap.push(val);    cout << "\n元素 " << val << " 入堆后" << endl;    printHeap(heap);}void testPop(priority_queue<int> &heap) {    int val = heap.top();    heap.pop();    cout << "\n堆顶元素 " << val << " 出堆后" << endl;    printHeap(heap);}int main() {    priority_queue<int, vector<int>,less<int>> maxHeap;    cout << "\n以下测试样例为大顶堆" << endl;    testPush(maxHeap, 1);    testPush(maxHeap, 3);    testPush(maxHeap, 2);    testPush(maxHeap, 5);    testPush(maxHeap, 4);    int peek = maxHeap.top();    cout << "\n堆顶元素为 " << peek << endl;    testPop(maxHeap);    testPop(maxHeap);    testPop(maxHeap);    testPop(maxHeap);    testPop(maxHeap);    int size = maxHeap.size();    cout << "\n堆元素数量为 " << size << endl;    bool isEmpty = maxHeap.empty();    cout << "\n堆是否为空 " << isEmpty << endl;    vector<int> input {1,3,2,5,4};    priority_queue<int,vector<int>,greater<int>> minHeap (input.begin(),input.end());    cout << "输入列表并建立小顶堆后" << endl;    printHeap(minHeap);    return 0;}

输出

以下测试样例为大顶堆元素 1 入堆后堆的数组表示：[1 ]堆的树状表示：——— 1元素 3 入堆后堆的数组表示：[3, 1 ]堆的树状表示：——— 3     \——— 1元素 2 入堆后堆的数组表示：[3, 1, 2 ]堆的树状表示：     /——— 2——— 3     \——— 1元素 5 入堆后堆的数组表示：[5, 3, 2, 1 ]堆的树状表示：     /——— 2——— 5     \——— 3          \——— 1元素 4 入堆后堆的数组表示：[5, 4, 2, 1, 3 ]堆的树状表示：     /——— 2——— 5   |     /——— 3     \——— 4          \——— 1堆顶元素为 5堆顶元素 5 出堆后堆的数组表示：[4, 3, 2, 1 ]堆的树状表示：     /——— 2——— 4     \——— 3          \——— 1堆顶元素 4 出堆后堆的数组表示：[3, 1, 2 ]堆的树状表示：     /——— 2——— 3     \——— 1堆顶元素 3 出堆后堆的数组表示：[2, 1 ]堆的树状表示：——— 2     \——— 1堆顶元素 2 出堆后堆的数组表示：[1 ]堆的树状表示：——— 1堆顶元素 1 出堆后堆的数组表示：[ ]堆的树状表示：堆元素数量为 0堆是否为空 1输入列表并建立小顶堆后堆的数组表示：[1, 3, 2, 5, 4 ]堆的树状表示：     /——— 2——— 1   |     /——— 4     \——— 3          \——— 5

提示：输出结果从右向左看会是想构造的树