愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

二叉最小堆

二叉堆是指用二叉树来实现堆这一种数据结构

堆的基本操作

1、插入一个数值

插入一个数值,要保持堆顶是最小的,我们可以将新插入的数值放在堆的末尾,然后通过向上和父节点比较来交换位置。如:

  • 1.1 在堆中插入0,我们先将0放在堆的末尾
  • 1.2 0和父节点2比较,比2小,和2交换位置
  • 1.3 0和父节点1比较,比1小,和1交换位置

2、取出最小值

把堆尾的指先拿来代替堆顶,然后向下比较,和左右儿子中最小的一个交换位置即可

实现思路

由于堆的二叉树中,节点是从上到下,从左到右紧凑排列的,所以,我们可以对节点从0开始编号,然后容易得知节点之间所具有的数学关系:
1、当前节点i,它的父节点编号为(i-1)/2(int类型自动丢掉小数部分)
2、当前节点i,它的左儿子编号为i2+1,右儿子编号为i2+2

代码实现

#include <cstdio>
#include <iostream>
using namespace std;

class MinHeap {
private:
    int* heap;
    int  size;
public:
    MinHeap(int maxHeapSize) {
        this->heap = new int[maxHeapSize];
        this->size = 0;
    }
    // 获取父节点编号
    int parentOf(int i) {
        return (i-1)/2;
    }
    // 获取左儿子节点编号
    int leftChildOf(int i) {
        return i*2+1;
    }
    // 获取右儿子节点编号
    int rightChildOf(int i) {
        return i*2+2;
    }
    // 插入数值操作
    void push(int x) {
        int i = this->size++;
        while(i > 0) {
            int p = this->parentOf(i);
            if(x < this->heap[p]) break;
            this->heap[i] = this->heap[p];
            i = p; 
        }
        this->heap[i] = x;
    }
    // 取出最小值操作
    int pop() {
        int min = this->heap[0];
        int x   = this->heap[--this->size];
        int i   = 0;
        while(i*2+1 < this->size) {
            int a = this->leftChildOf(i);
            int b = this->rightChildOf(i);
            int smaller = a<b ? a : b;
            if(x < this->heap[smaller]) break;

            this->heap[i] = this->heap[smaller];
            i = smaller; 
        }
        this->heap[i] = x;
        return min;
    }
};