结构

完全二叉树（并不是满二叉树）
底层是数组

分类

• 最大堆
  每个结点的值都大于或等于其左右孩子结点的值
• 最小堆
  每个结点的值都小于或等于其左右孩子结点的值

最大堆性质

父节点大于所有子节点，但是左右子节点

功能:

维护动态数据的最大最小值,可以考虑使用堆
调整堆的时间复杂度O(logk)

堆的操作(以小顶堆为例)

https://www.acwing.com/blog/content/308/

heap[++size] = x;up(size); //插入一个数
heap[1]; //求最小值
heap[1] = heap[size];size--;down(1); //删除最小值
heap[k] = heap[size];size--;down(k);up(k); //删除任意一个元素
heap[k] = x;down(k);up[k]; //修改任意一个元素

• down和up的时间复杂度为O(logn)最多交换深度h - 1次,h为n的log函数

down()

循环down

• 图1 循环down,注意是fa的左侧子节点存在,即<heapSize的时候.其实还是递归比较好理解
• 注意else的break;
• 注意nums[ minmum ] 而不是u,因为两个minmum可能因为赋值会不一样

void down(vector<int>& nums, int u, int heapSize) {
    //图1 循环down,注意是fa的左侧子节点存在,即<heapSize的时候.其实还是递归比较好理解
    //注意else的break;
    //注意nums[  minmum   ] 而不是u,因为两个minmum可能因为赋值会不一样
    while (u * 2 + 1 < heapSize) {
        int l = u * 2 + 1, r = u * 2 + 2, minmum = u;
        if (l < heapSize && nums[l] < nums[minmum]) {
            minmum = l;
        }
        if (r < heapSize && nums[r] < nums[minmum]) {
            minmum = r;
        }

        if (u != minmum) {
            swap(nums[u], nums[minmum]);
            u = minmum;
        }
        else {
            break;
        }
    }
}

图1

递归down

void down(vector<int>& nums, int u, int heapSize) {
    // 递归down
    int l = u * 2 + 1, r = u * 2 + 2, minmum = u;
    if (l < heapSize && nums[l] < nums[minmum]) {
        minmum = l;
    }
    if (r < heapSize && nums[r] < nums[minmum]) {
        minmum = r;
    }
    if (u != minmum) {
        swap(nums[u], nums[minmum]);
        down(nums, minmum, heapSize);
    }
}

up()

循环up

void up(vector<int>& nums, int u, int heapSize) {
    while (u && nums[(u - 1) / 2] > nums[u]) {
        swap(nums[(u - 1) / 2], nums[u]);
        u = u - 1 / 2;
    }        
}

递归up

void up(vector<int>& nums, int u, int heapSize) {
    int fa = (u - 1) / 2;
    if (u != 0 && nums[fa] > nums[u]) {
        swap(nums[fa], nums[u]);
        up(nums, fa, heapSize);
    }  
}

建堆

https://www.acwing.com/activity/content/code/content/493331/

• 时间复杂度为O(n),为什么?

  
  

void buildMinHeap(vector<int>& nums, int heapSize) {
    for (int i = heapSize / 2; i >= 0; --i) {
         down(nums, i, heapSize);
    }
}

heapify

使得数组“堆有序”

• 一定是全部有序吗？为什么
  不是，无法确定子节点左右大小

• 那堆排序如何实现？
  小顶堆,交换top和rear的位置,size--;down(top).这样数组从大到小排列
  交换n次,每次down的时间复杂度为O(logn)时间复杂度为O(nlogn)

  
  

较小值下沉
void maxHeapify(vector<int>& a, int i, int heapsize) {
    //如果是基1的,那么l = i * 2, r = i * 2 + 1
    int l = i * 2 + 1, r = i * 2 + 2, largest = i;
    if (l < heapSize && a[l] > a[largest]) {
        largest = l;
    }
    if (r < heapSize && a[r] > a[largest]) {
        largest = r;
    }
    if (largest != i) {
        //交换i和字节中的最大值
        swap(a[largest], a[i]);
        //较小值下沉
        maxHeapify(a, largest, heapSize);
    }
}

buildheap

void buildMaxHeap(vector<int>& a, int heapSize) {
    for (int i = heapSize / 2; i >= 0; --i) {
        maxHeapify(a, i, heapSize);
    } 
}

• heapsize不减的话一定会多做两次heapify。（其实问题不大）

LeetCode相关题目

215. 数组中的第K个最大元素