堆数据结构是一种数组对象，它可以被视为一颗完全二叉树结构（或者也有可能是满二叉树）
最大堆：任一结点的关键码均大于等于它的左右孩子的关键码，其中堆顶的元素最大。（任一路径中的元素升序排列）
最小堆：任一结点的关键码均小于等于它的左右孩子的关键码，其中堆顶的元素最小。（任一路径中的元素升序排列）
已知父节点：左孩子节点 = 2*父节点+1
右孩子节点 = 2*父节点+2
父节点 = （孩子节点-1）/ 2
堆的应用 优先级队列堆排序100W个数中找出最大（最小）的前K个数 最大堆和最小堆的实现 Heap.h #pragma once#include<iostream>#include<assert.h>#include<vector>using namespace std;template<class T>struct Less{ bool operator()(const T& left, const T& right) const { return left < right; }};template<class T>struct Greater{ bool operator()(const T& left, const T& right) const { return left > right; }};template<class T, class Compare=Less<T>>class Heap{public: Heap()//无参的构造函数（系统不会给无参构造函数），开始堆是空的不需要做什么事 {} Heap(T* a, size_t n) { _a.reserve(n);//开空间 for (size_t i = 0; i < n; ++i) { _a.push_back(a[i]); } //建堆,找最后一个非叶子节点 for (int i = (_a.size() - 2) / 2; i >= 0; --i)//不用size_t，因为i在这可能等于0，用size_t会死循环 { AdjustDown(i); } } //向下调整 void AdjustDown(int root) { Compare com; int parent = root; size_t child = parent * 2 + 1;//默认为左孩子 while (child < _a.size()) { //选出小孩子 //if (child+1 > _a.size() && _a[child + 1]< _a[child]) if (child + 1 < _a.size() && com(_a[child + 1], _a[child])) { ++child; } //if (_a[child] < _a[parent]) if (com(_a[child], _a[parent])) { swap(_a[child], _a[parent]);//交换值 parent = child; child = parent * 2 + 1; } else { break; } } } //向上调整 void AdjustUp(int child) { Compare com; int parent = (child - 1) / 2; while (parent >= 0) { //if (_a[child] < _a[parent]) if (com(_a[child], _a[parent])) { swap(_a[parent], _a[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } //最后插入 void Push(const T&x) { _a.push_back(x); AdjustUp(_a.size() - 1); } //删除最大数 void Pop() { assert(!_a.empty()); swap(_a[0], _a[_a.size() - 1]); _a.pop_back(); AdjustDown(0); } //取顶元素 T& Top() { assert(!_a.empty()); return _a[0]; } size_t Size() { return _a.size(); } bool Empty() { return _a.empty(); }private: vector<T> _a;}; test.cpp #include <iostream>#include "Heap.h"using namespace std;int main(){ int a[] = {10,11,13,12,16,18,15,17,14,19}; // Heap<int,Greater<int>> hp1(a,sizeof(a)/sizeof(a[0])); 最大堆 // Heap<int,Less<int>> hp1(a,sizeof(a)/sizeof(a[0])); 最小堆 Heap<int> hp1(a,sizeof(a)/sizeof(a[0])); // 缺省，最小堆 hp1.Push(15); return 0;} 运行结果： 测试最大堆： 测试最小堆：