----------------

该篇文章经提醒有一些错误，暂时没有时间修改，请勿参考。

该篇文章经提醒有一些错误，暂时没有时间修改，请勿参考。

----------------

堆是特殊的队列，从堆中取元素是按照元素的优先级大小，而不是元素进入队列的先后顺序。因此，堆也通常被称为“优先队列”。

堆的最常用结构是用二叉树表示，不特指的话，他是一棵完全二叉树。因此通常不必用指针，而是用数组来实现堆的存储。我们

知道，完全二叉树用数组来表示，就相当于把全完二叉树的层序遍历依次存入数组中，知道最后一个节点。

需要注意的是，所用的数组的起点为1，而不是0。这样的目的是很容易能够从父节点(i)找到子节点[ 2i ] [ 2i+1 ]，反过来也很容易从子节点(j)找到父节点[ j/2 ]。 

堆的特性：

用数组来表示完全二叉树是堆的第一特性：堆的结构特性。

任一节点的值与其子节点的值是相关的：部分有序性。

相关性的不同决定了两种不同的基本堆：最大堆(MaxHeap)(任一节点大于等于其子节点)和最小堆(MinHeap)(任一节点小于等于其子节点)。注意，兄弟节点之间没有约束关系。

当我们需要小键值优先时，使用最小堆；需要大键值优先时，使用最大堆。

首先来看一下堆的一般结构体实现:

typedef struct HNode * heap;//结构体指针
struct HNode{
    ElementType *Data;//表示堆的数组 大小要在用户输入的元素个数上+1
    int Size;//数组里已有的元素(不包含a[0]) 
    int Capacity; //数组的数量上限
};
typedef heap MaxHeap; //定义一个最大堆
typedef heap MinHeap; //定义一个最小堆

创建：

//mheap表示maxHeap或者minHeap
mHeap creatMHeap(int size){
    mHeap heap = (mHeap)malloc(sizeof(struct Hnode));
    heap->data = (int*)malloc(sizeof(int)*(size+1));//从a[1]开始保存数 所以数组数量要+1
    heap->Size = 0;
    heap->Capacity=size;
    heap->data[0] = MAXData OR MINDATA;//岗哨 稍后会提到
    return heap;
}

接下来用代码来表示最大堆和最小堆的相关操作：

最大堆(MaxHeap):

插入：

从新增的最后一个节点的父节点开始，用要插入的元素向下过滤上层节点(比该元素小的下移)。

bool insertToHeap(maxHeap heap, int x){
    //查看是否已经满了
    if (heap->Size == heap->Capacity) {
        return false;
    }
    int i = ++heap->Size;//新增的节点位置
    for (; heap->data[i/2]<x; i/=2) {
//此处的判断 如果向上到了a[1]还没停止的话 需要让其就停在a[1]处 所以要在a[0]的位置放置一个"岗哨"
//这个岗哨对于最大堆来说要放入一个 比数组中所有数都大的数 这样在比较a[0]和x时 a[0]>x 循环就会停下来
        heap->data[i] = heap->data[i/2];
    }
    heap->data[i] = x;
    return true;
}

删除：

从根节点开始，用最大堆中的最后一个元素向上过滤下层节点(比该元素大的上移)。

int deleteHeap(maxHeap heap){
    //判断是否空
    if (heap->Size==0) {
        return false;
    }
    int top = heap->data[1];//堆顶元素(最大)
    int last = heap->Size--;//取出数组最后一个元素
    int parent = 1;
    int child;
    for (; parent*2<=heap->Size; parent=child) {
        child = 2*parent;//左子节点
        //查找是否有右子节点 并且 右子节点的元素大于左子节点
        if (child!=heap->Size && heap->data[child]<heap->data[child+1]) {
            child++;//右子节点
            if (last<heap->data[child]) {
                heap->data[parent] = heap->data[child];
            }else{//找到了位置
                break;
            }
        }
    }
    heap->data[parent] = last;
    return top;
}

构造：

虽说构造一个最大堆时只要把一个个元素按照插入方法插入到数组中即可完成。但是其时间复杂度是(O(N log N))。我们有一种更简单的方式，使得时间复杂度下降到O(N)。

1.将输入的元素按顺序放入完全二叉树(数组)中。

2.调整各个节点的位置，满足最大堆的有序性。

调整的过程就是从最后一个父节点开始倒序到根节点，逐一向下进行过滤操作(同删除的向下过滤一样，不过过滤元素就是父节点本身的元素)。

void percDown(maxHeap heap, int n){
    int top,parent,child;
    top = heap->data[n];//取出父节点元素
    //向下过滤
    for (parent = n; parent*2<heap->Size; parent=child) {
        child = 2*parent;
        if (child!=heap->Size && heap->data[child]<heap->data[child+1]) {
            child++;
            if (heap->data[child]<=n) {
                break;
            }else
                heap->data[child] = heap->data[parent];
        }
    }
    heap->data[parent] = top;
}

void buildMaxHeap(maxHeap heap){
    for (int i=heap->Size/2; i>0; i--) {//从最后一个父节点开始
        percDown(heap, i);
    }
}

最小堆(MaxHeap):

由于最大堆和最小堆只是元素的顺序位置不同，具体的操作只是细节判断的修改，就只提下插入和删除操作把：

插入：

bool insertMinHeap(minHeap heap, int x){
    //判断是否满了
    if (heap->Size == heap->Capacity){
        return false;
    }
    int p = ++heap->Size;
    for (; heap->data[p/2]<x; p/=2) {
//这里是最小堆  所以在a[0]位置的岗哨保存了比数组中所有元素都小的元素
        heap->data[p] = heap->data[p/2];
    }
    heap->data[p] = x;
    return true;
}

删除：

int deleteFromMinHeap(minHeap heap){
    int top = heap->data[1];
    int last = heap->data[heap->Size--];
    int parent,child;
    for (parent = 1; parent*2<heap->Size; parent=child) {
        child = parent*2;
            //注意这里是存在右子节点 并且 右子节点比左子节点小    
        if (child!=heap->Size && heap->data[child] > heap->data[child+1]) {
            child++;
            //如果比右子节点还小
            if (heap->data[child]>last) {
                break;
            }else{//下滤
                heap->data[parent] = heap->data[child];
            }
        }
    }
    heap->data[parent] = last;
    return top;
}

• 堆的属性

1. 完全二叉树
2. 每个节点的值都大于（最大堆）或都小于（最小堆）子节点的值

堆只是一种数据的组织形式，存储结构可以用数组，在构建堆的过程中，可以使用完全二叉树的性质求父子节点的下标。

父节点的下标 = 向下取整 ( (子节点下标 - 1) /  2)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
void minheap();
void maxheap();
using namespace std;
int arr[8] = { 53,17,78,9,45,65,87,23 };
int *a = new int[8];//保存小根堆
int index = 0;
int main()
{
    minheap();
    cout << "建立的最小堆为：" << endl;
    for (int i = 0; i < 8; i++)
    {
        cout << a[i] <<" ";
    }
    system("pause");
}

void maxheap() {
  while(index < 8) {
    a[index] = arr[index];
    if (index != 0) {
      int son_index = index;
      int par_index = floor((son_index - 1) / 2);
      while(a[par_index] < a[son_index]) {
        int tmp = a[par_index];
        a[par_index] = a[son_index];
        a[son_index] = tmp;
        son_index = par_index;
        par_index = floor((par_index - 1) / 2);
      }
    }
    index ++;
  }
}
void minheap()
{
  while (index < 8) {
    a[index] = arr[index];
    if (index != 0) {
      int son_index = index;
      int par_index = floor((son_index - 1) / 2);
      while (a[par_index] > a[son_index]) {//小根堆:父节点大的话需要交换
          int temp = a[par_index];//交换
          a[par_index] = a[son_index];
          a[son_index] = temp;
          son_index = par_index;//迭代看之前的是否需要调整
          par_index = floor((son_index - 1) / 2);
      }
    }
    index ++;
  }
}

目录

首先来看一下什么是最大堆和最小堆？

python heapq库中的一些常用方法

小试牛刀

首先来看一下什么是最大堆和最小堆？

最大堆：一种经过排序的完全二叉树，其中任意非终端节点数值均不小于其左子节点和右子节点的值。如果一颗二叉树满足最小堆的要求，那么，堆顶（根节点）也就是整个序列的最大元素。

最小堆：也是一种经过排序的完全二叉树，其中任意非终端节点数值均不大于其左子节点和右子节点的值。如果一棵二叉树满足最小堆的要求，那么，堆顶（根节点）也就是整个序列的最小元素。

python heapq库中的一些常用方法

注意：python中的heapq库只有最小堆，没有最大堆，当使用最大堆时，可以在插入元素时将元素取反，弹出是也取反，一些常用操作如下：

import heapq
# [2,0,4,1]

# 1.创建堆
# 方法一：定义一个空列表，然后使用heapq.heqppush(item)函数把元素加入到堆中
item = 2
heap = []
heapq.heappush(heap,item)
# 方法二：使用heapq.heapify(list)将列表转换为堆结构
heap = [2,0,4,1]
heapq.heapify(heap)

# 2.heapq.heappush() 添加新元素 num
num = 3
heapq.heappush(heap,num)

# 3.heapq.heappop() 删除并返回堆顶元素
heapq.heappop(heap)

# 4.heapq.heappushpop() 比较添加元素num与堆顶元素的大小:如果num>堆顶元素，删除并返回堆顶元素，然后添加新元素num;如果num<堆顶元素，返回num，原堆不变
# 其实也就等价于 添加新元素num，然后删除并返回堆顶元素
num = 0
heapq.heappushpop(heap,num)

# 5.heapq.heapreplace() 删除并返回堆顶元素，然后添加新元素num
num = 5
heapq.heapreplace(heap,num)

# 6. heapq.merge() 合并多个排序后的序列成一个排序后的序列， 返回排序后的值的迭代器。
heap1 = [1,3,5,7]
heap2 = [2,4,6,8]
heap = heapq.merge(heap1,heap2)
print(list(heap))

# 7.heapq.nsmallest() 查询堆中的最小n个元素
n = 3
heap = [1,3,5,7,2,4,6,8]
print(heapq.nsmallest(n,heap)) # [1,2,3]

# 8.heapq.nlargest() 查询堆中的最大n个元素
n = 3
heap = [1,3,5,7,2,4,6,8]
print(heapq.nlargest(n,heap)) # [8,7,6]

小试牛刀

题目1：剑指 Offer 40. 最小的k个数

# 最大堆解法，参考题解：https://www.bilibili.com/video/BV1To4y1d7cW/
import heapq
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k == 0:
            return []
        # python中只有最小堆，没有最大堆
        # 将所有元素取反，弹出的时候也取反
        heap = [-x for x in arr[0:k]]
        heapq.heapify(heap)
        for x in arr[k:]:
            if -x > heap[0]:
                heapq.heapreplace(heap,-x)
        return [-x for x in heap]

题目2：剑指 Offer 41. 数据流中的中位数

# 最大堆最小堆解法，参考题解:https://www.bilibili.com/video/BV1J5411J7yj/
import heapq
class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.maxHeap = [] # 最大堆保存的是最小的n/2个数
        self.minHeap = [] # 最小堆保存的是最大的n/2个数

    def addNum(self, num: int) -> None:
        # 若两堆的数目相等，就让minHeap的元素个数+1
        # 具体做法分为两步 1.将新元素加入maxHeap 2.将maxHeap的堆顶元素加入minHeap
        if len(self.maxHeap)==len(self.minHeap):
            heapq.heappush(self.minHeap,-heapq.heappushpop(self.maxHeap,-num))
        else:
            heapq.heappush(self.maxHeap,-heapq.heappushpop(self.minHeap,num))
            
    def findMedian(self) -> float:
        if len(self.maxHeap)==len(self.minHeap):
            return (self.minHeap[0]-self.maxHeap[0])/2.0
        else:
            return self.minHeap[0]