【Tutorial】堆和优先队列

【Tutorial】堆和优先队列

堆的定义和分类
- 堆与优先队列
  - 优先队列：一种抽象的数据类型，优先队列中每个元素都有自己的优先级，优先级高的元素最先得到服务，优先级相同的元素按照在优先队列中的顺序得到服务。
  - 堆：是一种数据结构，是实现优先队列的一种方式
  - 优先队列的插入和删除操作中，一种可以在O(1)的时间复杂度内完成，另一种则需要在O(N)的时间复杂度内完成
  - 堆可以使得数据的插入和删除操作都在O(logN)的时间复杂度内完成
- 堆的定义：
  - 堆是一种特殊的二叉树，满足如下条件的二叉树可以称之为堆：
    - 完全二叉树
    - 每一个节点的值必须 大于等于 或 小于等于 其孩子节点的值
  - 堆的相关操作的特点如下：
    - 可以在 O(1)的时间复杂度内获取堆中的最大值或最小值
    - 可以在O(logN)的时间复杂度向堆中插入或删除元素
  - 堆的分类
    - 最大堆
      - 每一个节点的值都大于等于其孩子节点的值，根节点/堆顶元素是堆中的最大值
    - 最小堆
      - 每一个节点的值都小于等于其孩子节点的值，根节点/堆顶元素是堆中的最小值
- 堆的插入
  - 最小（大）堆的插入
    - 先插入最后，满足完全二叉树
    - 对比父节点，不符合条件从叶子节点到根节点依次交换元素
- 堆的删除
  - 最小堆的删除
    - 将最后一个元素移到堆顶，删除最后一个元素
    - 移动到堆顶的元素与最小的孩子节点不断依次交换，直到不再大于左孩子节点或到达堆末尾。
  - 最大堆的删除
    - 将最后一个元素移到堆顶，删除最后一个元素
    - 移动到堆顶的元素与孩子节点比较，不断交换直到不小于孩子节点或到达堆末尾
- 堆的实现（手动）
- /*
- 最大堆
- */
- template
- class MaxHeap {
- private:
- T* mHeap; //data
- int mCapacity;
- int mSize;
- static const int DEFAULT_SIZE = 30;
- private:
- // maxHeap 向下调整算法
- void filterDown(int start, int end);
- // maxHeap 向上调整算法
- void filterUp(int start);
- public:
- MaxHeap();
- MaxHeap(int mCapacity);
- ~MaxHeap();
- // return the index of data in maxHeap
- int getIndex(T data);
- //插入指定data并调整堆结构
- int insert(T data);
- //移除 maxHeap 中指定的data并调整堆结构
- int remove(T data);
- };
- /*
- - MaxHeap构造函数
- */
- template
- MaxHeap::MaxHeap() {
- new (this)MaxHeap(DEFAULT_SIZE);
- }
- template
- MaxHeap::MaxHeap(int capcaity) {
- mSize = 0;
- mCapacity = capcaity;
- mHeap = new T mHeap[capcaity];
- }
- /*
- - MaxHeap析构函数
- */
- template
- MaxHeap::~MaxHeap() {
- mSize = 0;
- mCapacity = 0;
- delete[] mHeap;
- }
- /*
- - 获得堆中相应元素索引
- - 返回值：
- - 存在 —— 返回data在堆中的索引
- - 不存在 —— 返回 -1
- */
- template
- int MaxHeap::getIndex(T data) {
- for (int i = 0; i < mSize; ++i)
- if (mHeap[i] == data)
- return i;
- return -1;
- }
- /*
- - 最大堆的向上调整算法，一般用于插入
- - 注：当前节点：N 左孩子节点：2N + 1 右孩子节点：2N + 2
- - 参数说明：
- - start —— 被上调节点的索引，一般为数组中最后一个元素的索引
- */
- template
- void MaxHeap::filterUp(int start) {
- int c = start; //当前节点下标
- int p = (c - 1) / 2; //父亲节点下标
- T elem = mHeap[c]; //当前节点的元素
- while (c > 0) {
- if (mHeap[p] >= elem)
- break;
- mHeap[c] = mHeap[p];
- c = p;
- p = (p - 1) / 2;
- }
- mHeap[c] = elem;
- }
- /*
- - 最大堆中插入元素
- - 返回值：
- - 0 —— 插入成功
- - -1 —— 插入失败
- */
- template
- int MaxHeap::insert(T data) {
- //堆满
- if (mSize == mCapacity)
- return -1;
- mHeap[mSize] = data; //数据先放入堆尾
- filterUp(mSize); //插入数据，向上调整元素
- mSize++; //更新堆大小
- return 0;
- }
- /*
- - 最大堆的向下调整算法，一般用删除
- - 参数说明：
- - start - 被调整节点下标，一般为0
- - end - 调整范围，一般到堆末尾，最大为mSize -1
- *
- */
- template
- void MaxHeap::filterDown(int start, int end) {
- int c = start; //当前节点的下标
- int l = 2 * c + 1; //左子节点下标
- T elem = mHeap[c]; //当前节点对应值
- while (l <= end) {
- // l是左子节点，r是右子节点
- // 两子节点选择较大者（为啥
- if (l < end && mHeap[l] < mHeap[l + 1])
- l++;
- if (elem >= mHeap[l])
- break;
- mHeap[c] = mHeap[l];
- c = l;
- l = l * 2 + 1;
- }
- mHeap[c] = elem;
- }
- /*
- - 删除堆中的元素
- - 返回值：
- - 0 —— 成功
- - -1 —— 失败
- */
- template
- int MaxHeap::remove(T data) {
- //堆空不需要删除
- if (mSize == 0)
- return -1;
- int index = getIndex(data);
- //若data在堆中不存在，也不需要删除
- if (index == -1)
- return -1;
- //删除当前节点元素，用堆尾元素递补
- mHeap[index] = mHeap[—mSize];
- filterDown(index, mSize - 1);
- return 0;
- }
- 堆的实现(priority_queue)
  - 大顶堆（最大堆）：priority_queue, less>
  - 小顶堆（最小堆）：priority_queue, greater<int>>
  - 入堆：push()，时间复杂度:O(logN)
  - 出堆：pop()，时间复杂度：O(logN)
  - 取堆顶元素：top()