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

Regan Yue

关注

发布于: 刚刚

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

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;      }          }  }
}

复制代码

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

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

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/7e0b7820f4fdc5d5333e7ee87】。

Regan Yue

关注

还未添加个人签名 2020.08.12 加入

对Go、Python、网络安全、区块链感兴趣. · 华为云云享专家 · 掘金资讯创作者

发布

暂无评论

创作场景

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

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

0x00 前言

0x01 插入操作

0x02 删除操作

0x03 更新操作

Regan Yue

评论