二叉堆的定义

  • 二叉堆(英语:binary heap)是一种特殊的堆,二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆。

  • 当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆(大根堆)”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆(小根堆)”。

  • image.png

  • image.png

二叉堆的操作

  • 变量介绍

    • heap[i] -> 表示二叉堆的第 i 个结点保存的值
    • sz -> 当前二叉堆中的元素个数
  • 堆的定义

    • 	const int N = 1e5 + 5;
      	int heap[N], sz;
      
  • 向小根堆中插入数据

    • 我们每次插入数据,在二叉堆最后一个结点后面添加一个新的结点。然后通过相邻层元素的上移动,来确定插入结点应该在的位置,使得新插入的结点不会破坏 小根堆 的特性。
    • 	void up(int u) {
      		while (u / 2 > 0 && heap[u] > heap[u / 2]) // 判断当前点是否小于父结点的值,如果小于则交换值
      		{
      			swap(heap[u], heap[u/2]);
      			u = u / 2; // u >>= 1;
      		}
      	}
      
      	void insert(int x) {
      		heap[++ sz] = x;
      		up(sz); // 将新插入的结点与其父结点比较	
      	}
      
  • 获取最小值

    • 直接输出小根堆的堆顶
    • 	int top(){
      		return heap[1];
      	}
      
  • 删除最小值

    • 将堆顶(根),与最后一个结点交换,然后sz --, 在将堆顶移动到对应位置
    • 	void down(int u) {
      		int t = u;
      		if (u * 2 <= sz && heap[u * 2] < heap[t]) t = u * 2;		// 与它的左子结点比较,取最小值
      		if (u * 2 + 1 <= sz heap[u * 2 + 1] < heap[t]) t = u * 2 + 1; 	// 与它的右子结点比较,与取的最小值比较
      		if (u != t) {
      			swap(heap[u], heap[t]);
      			down(t); // 递归到下一层判断
      		}
      	}
      
      	void pop() {
      		heap[1] = heap[sz];
      		sz --;
      		down(1);
      	}
      

二叉堆的题目

  1. 输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。

    • 题目链接:堆排序

    • 该题目就是一个模板题目,和上面说的差不多

    • 
      	#include <iostream>
      	#include <algorithm>
      	using namespace std;
      
      
      	const int N = 1e5 + 5;
      
      	int heap[N], sz;
      
      
      	void down(int u) {
      	    int t = u;
      	    if (u * 2 <= sz && heap[u * 2] < heap[t]) t = u * 2;
      	    if (u * 2 + 1 <= sz && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
      
      	    if (t != u) {
      	        swap(heap[u], heap[t]);
      	        down(t);
      	    }
      	}
      
      	int main() {
      	    int n, m;
      	    cin >> n >> m;
      	    sz = n;
      
      	    for (int i = 1; i <= n; ++ i) cin >> heap[i]; // 先向堆中输入值
      
      	    for (int i = n/2; i > 0; -- i) down(i); // O(N) 建堆,从倒数第二层开始
      
      	    for (int i = 0; i < m; ++ i) {
      	        cout << heap[1] << " ";
      	        heap[1] = heap[sz --];
      	        down(1);
      	    }
      
      	    cout << endl;
      
      	    return 0;
      	}
      
    • 建立堆那里解释一下

      • image.png
      • image.png
  2. 维护一个集合,初始时集合为空,支持如下几种操作:I x,插入一个数 x;PM,输出当前集合中的最小值;DM,删除当前集合中最小值(数据保证此时的最小值唯一);D k,删除第 k 个插入的数;C k x,修改第 k 个插入的数,将其变为 x;现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小值。

    • 题目链接:模拟堆
    • 这个题的后两个操作需要知道 第k个插入的树在 堆中哪个结点,还有堆中结点映射到第几个个插入
    • 解题:
      • 变量介绍
        • heap[N] -> 二叉堆
        • sz -> 堆当前元素的个数
        • cnt -> 记录插入了几个数
        • ph[i] -> 第 i 个插入的数,在二叉堆的ph[i] 的位置
        • hp[i] -> 二叉堆 第 i 个结点,保存的是第 hp[i] 个插入的值
      • 定义变量
        • 	const int N = 1e5 + 5;
          	int heap[N], ph[N], hp[N], cnt, sz;
          
      • 重写交换函数
        • 因为这次交换不仅仅要交换对应结点的值,还有映射信息
        • image.png
        • 	void head_swap(int a, int b) {
          		swap(heap[a], heap[b]);
          		swap(ph[hp[a]], ph[hp[b]]);
          		swap(hp[a], hp[b]);
          	}
          
      • 插入一个值到二叉堆里面
        • image.png
        • 
          	void up(int x) {
          		while (u / 2 > 0 && heap[u] > heap[u / 2]) // 判断当前点是否小于父结点的值,如果小于则交换值
          
          		heap_swap(u, u/2);
          		u = u / 2; // u >>= 1;
          
          	}
          	void insert(int x) {
          		heap[++ sz] = x;
          		ph[++ cnt] = sz;
          		hp[sz] = cnt;
          		up(sz);
          	}
          
          
      • 删除小根堆的最小值(堆顶)
        • image.png
        • 	void down(int u) {
          		 int t = u;
          		 if (u * 2 <= sz && heap[u * 2] < heap[t]) t = u * 2;
          		 if (u * 2 + 1 <= sz && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
          
          		 if (t != u) {
            		 heap_swap(u, t);
            		 down(t);
          		 }
          	}
          	void pop() {
          		heap_swap(1, sz);
          		sz --;
          		down(1);
          
          	}
          
      • 删除第 k 个插入的数
        • 	void deleteKth(int k) {
          		int u = ph[k];
          		heap_swap(u, sz);
          		sz --;
          		up(u), down(u);
          	}
          
          
      • 修改第k个插入的数
        • 	void updateKth(int k, int x) {
          		heap[ph[k]] = x;
          		up(ph[k]), down(ph[k]);
          	}
          
    • 完整解题代码
      • 	#include <iostream>
        	#include <algorithm>
        	#include <string>
        	using namespace std;
        
        	const int N = 1e5 + 5;
        	int heap[N], sz, cnt, ph[N], hp[N];
        
        	void heap_swap(int a, int b) {
        	    swap(heap[a], heap[b]);
        	    swap(hp[a], hp[b]);
        	    swap(ph[hp[a]], ph[hp[b]]);
        
        
        	}
        
        	void up(int u) {
        	    int t = u;
        
        	    while (t / 2 > 0 && heap[t] < heap[t / 2]) {
        	        heap_swap(t, t/2);
        	        t = t / 2;
        	    }
        	}
        
        	void down(int u) {
        	    int t = u;
        	    if (u * 2 <= sz && heap[u * 2] < heap[t]) t = u * 2;
        	    if (u * 2 + 1 <= sz && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
        	    if (t != u) {
        	        heap_swap(t, u);
        	        down(t);
        	    }
        	}
        
        	void insert(int x) {
        	    heap[++sz] = x;
        	    ph[++cnt] = sz;
        	    hp[sz] = cnt;
        
        	    up(sz);
        	}
        
        
        	int top() {
        	    return heap[1];
        	}
        
        	int pop() {
        	   int x = heap[1];
        	   heap_swap(1, sz);
        	   sz --;
        	   down(1);
        	   return x;
        	}
        
        	void deleteKth(int k) {
        	    int u = ph[k];
        	    heap_swap(u, sz);
        	    sz --;
        	    up(u);
        	    down(u);
        	}
        
        	void updateKth(int k, int x) {
        	    heap[ph[k]] = x;
        	    up(ph[k]);
        	    down(ph[k]);
        	}
        
        	int main() {
        
        	    int n;
        	    cin >> n;
        
        	    while (n --) {
        	        string op;
        	        int k, x;
        	        cin >> op;
        	        if (op == "I") {
        	            cin >> x;
        	            insert(x);
        	        } else if (op == "PM") {
        	            cout << top() << endl;
        	        } else if (op == "DM") {
        	            pop();
        	        } else if (op == "D") {
        	            cin >> k;
        	            deleteKth(k);
        	        } else if (op == "C") {
        	            cin >> k >> x;
        	            updateKth(k, x);
        	        }
        	    }
        	}