谈一谈最小二叉堆的几种操作

谈一谈最小二叉堆的几种操作

0x00 前言

今天我们来谈一谈最小二叉堆的三种操作——插入、删除、更新。先来介绍一下什么是最小二叉堆，最小二叉堆也是一棵二叉树，最小二叉堆就是父节点一定比子节点小，也就是所有的父节点都比它的左右子节点要小。

关于怎么建堆，我这里就不细说了，因为是一颗完全二叉树，所以我们可以用数组来存储最小二叉堆。我们这里使用堆{6,2,3,4,5,6,7}。我们将最小二叉堆所在数组的第一个值设置为堆内元素的个数，这样能给后续操作带来便利。

0x01 插入操作

void insert( int x, int heap[]) {
    heap[heap[0]+1] = x;
    heap[0]++;
    int i = heap[0];
    while(i>1 && heap[i] < heap[i/2]) {
        swap(&heap[i],&heap[i/2]);
        i /= 2;
    }
}

前面我们说了，二叉堆所在数组也就是heap[0]，代表的是堆内元素个数。我们先将要插入的元素放置到堆的后一个位置，也就是heap[0]+1，然后将heap[0]也就是堆内元素个数自增。

然后设置循环，只要父节点大于子节点的值并且索引不等于0，就将父节点与子节点交换位置，并且将循环的索引放置到之前节点的父节点（也就是选择的节点索引）。

0x02 删除操作

int del( int heap[]) {
    int ele = heap[1];
    heap[1] = heap[heap[0]];
    heap[0]--;
    int i=1;
    int min;
    if( heap[2*i+1] > heap[2*i] ) {
        min = 2*i;
    } else {
        min = 2*i+1;
    }
    
    while(min<heap[0] && heap[i] > heap[min]) {
        swap(&heap[i],&heap[min]);
        i=min;
        if(heap[2*min+1] > heap[2*min]) {
            min = 2*min;
        } else {
            min = 2*min+1;
        }
    }
    return ele;
}

这个思路就稍微复杂一点，但是我们删除节点都是删除最顶端节点，然后将最后一个元素移到顶点，然后在调整堆的结构。因为要返回删除的元素值，所以定义一个ele保留删除的元素，然后用最后一个元素覆盖它。因为删除了一个元素，堆的元素个数减一，所以首元素自减。

最上方的节点索引是1，我们将此元素先与左右子节点中的最小值比较，如果大于其中的最小值，就将最小值的坐标赋给min。

然后进入循环，当min的索引不超过heap[0],也就是元素个数，并且当前节点的值大于左右子节点中的最小值，就交换他们的位置，然后将原来最小值的坐标赋给当前节点，然后再求左右子节点的最小值，再比较大小。

0x03 更新操作

void update( int x, int pos, int heap[], int len ) {
    if(heap[pos] > x) {
        heap[pos] = x;
        int i = pos;
        while(heap[i]<heap[i/2]) {
            swap(&heap[i],&heap[i/2]);
            i/=2;
        }
    }
    if(heap[pos] < x) {
        heap[pos] = x;
        int i=pos;
        int min;
        if( heap[2*i+1] > heap[2*i] ) {
            min = 2*i;
        } else {
            min = 2*i+1;
        }
​
        while(min<heap[0] && heap[i] > heap[min]) {
            swap(&heap[i],&heap[min]);
            i=min;
            if(heap[2*min+1] > heap[2*min]) {
                min = 2*min;
            } else {
                min = 2*min+1;
            }
            
        }
    }
​
}

更新操作就是上面两种方式的结合，如果更新后的值小于原来的值，就上升，和增加元素的操作一致。

如果更新后的值大于原来的值，就执行下降操作，也就是和删除元素的操作一致。