堆(Heap)是一种特殊的树形结构，也叫二分堆(Binary Heap)。

堆拥有以下特殊的结构：给定任意节点P和C，若P是C的父节点，那么P的值会大于等于（或小于等于）C的值，那么即可称为堆。所以有两种分类：

  • Max Heap 最大堆 – 父节点恒大于或等于子节点。
  • Min Heap 最小堆 – 父节点恒小于或等于子节点。

堆通常用以数组的方式实现，并且元素之间不需要指针。当插入元素或者删除元素的时候，常常会打破堆结构，需要重新平衡堆。以单独数组表示的二分堆，第一个元素是根节点，以0开始的数组，节点n的子节点的位置为2n+1和2n+2，而以1开始的数组，节点n的子节点的位置为2n和2n+1。设最大堆的结构如下：

class MaxHeap {
  int *harr;
  int capacity;
  int heap_size;
  public: 
    MaxHeap(int capacity);
    int parent(int i) { return (i-1)/2; }
    int left(int i) { return (2*i + 1); }
    int right(int i) { return (2*i + 2); }
    int findMax();
    int extractMax();
    void deleteKey(int i);
    void insertKey(int k);
}

MaxHeap::MaxHeap(int cap) {
  heap_size = 0;
  capacity = cap;
  harr = new int[cap];
}

堆的性质

堆具有以下性质：

  • 所有的节点必须大于（或小于）它的子节点，堆的最大值（或最小值）在堆的根上面。
  • 堆是一棵完全树。即除了最底层，其他层次的节点都被填满，且最底层也是从左往右填满。

堆的操作

以下操作以最大堆为例：

  • find-max: 在最大堆找到最大值，即是返回根节点。 
    int MaxHeap::findMax() {
return harr[0];
}
  • insert: 插入一个新值到堆里面
  • extract-max: 从最大堆中移除最大节点值，并返回值
  • create-heap: 创建一个空的堆
  • heapify: 从给定的元素数组创建一个堆。