二叉堆

今天我们来说一下二叉堆(BinaryHeap)。堆是很有用的数据结构,例如后面会学到的优先队列,堆排序等,都和堆有关。操作系统中很多调度,也和堆有关。

还记得我们之前学过的完全二叉树吗?如果不记得了,就需要先回去复习一下,因为二叉堆,首先是一棵完全二叉树,或者近似完全二叉树。

再来说一下二叉堆的特性。二叉堆分为最小堆和最大堆。如果是最小堆,那么父节点的值,总是小于或等于任何一个子节点的值,通俗点就是把一棵树从上往下看,值在变大,下面的大于等于上面的。如果是最大堆,则是反过来,父节点的值,总是大于或等于任何一个子节点的值。

如果要简单点记忆,那就是这棵树上的值按层来看,如果是从小到大,那就是最小堆,如果是从大到小,那就是最大堆。

接下来我们就开始说二叉堆的细节,插入节点,删除节点。

插入节点

插入节点,其实也就是构建二叉堆的过程,语言描述流程如下。

  1. 找到要插入的位置,这个位置就是当前这棵完全二叉树,最后一个位置 (不太好理解)。如果用代码流程来描述的话,就是按层遍历当前的树,如果遇到一个节点,左子树为空,或者又子树为空,或者左右子树都为空,那么,这个点就是要插入节点的父节点,而要插入的节点,将作为这个节点的左子树或右子树。看下面的图

p001901_Binary-Heap-1

假设我们要在上面的堆中插入一个节点,按照上面代码流程中描述的,可以找到要插入节点的父节点,是11。

  1. 找到了要插入节点的父节点,还要判断这个父节点是左子树为空,还是右子树为空,还是都为空,如果左子树为空,则新点作为左子树,如果左子树不为空,则新点作为右子树。插入后的图如下(假设要插入的数值为3)

p001902_Binary-Heap-2

  1. 节点插入后,当前的树并不满足二叉堆的规则,所以还需要将新插入的点向上浮动。如果当前节点值小于父节点的值,则交换当前节点和父节点的值。然后再次判断,直到当前值不再小于父节点值,或者父节点值为空了,则位置调整完毕,整个插入流程也就结束了。看下面的流程图

p001903_Binary-Heap-3

上图中,首先用 3 和 11 比较,因为 3 小于 11,所以交换两个节点的值

p001904_Binary-Heap-4

上图中,再次用 3 和父节点 5 比较,因为 3 小于 5,所以再次交换两个节点的值

p001905_Binary-Heap-5

上图中,再次用 3 和父节点 1 比较,咦,3 不小于 1,所以不交换,节点调整结束。此时的树满足二叉堆的规则。

以上就是整个插入节点的流程,下面我们用代码去实现一下。代码中的 TreeAlgo 类是我们为了方便写的一个帮助类,实现了层序打印和查找的一些方法。

// 定义节点的结构
public class Node {
public int data;
public Node parent = null;
public Node left = null;
public Node right = null;

public Node(int data){
this.data = data;
}
}
// 定义二叉堆操作类
using System;

public class BinaryHeap {
public Node root;

public void Insert(int data){
Node lastParentNode = TreeAlgo.FindParentOfFartestLeftLocation(root);
if(lastParentNode == null){
Console.WriteLine("Insert Root Node " + data);
root = new Node(data);
}else{
Node newNode = new Node(data);
if(lastParentNode.left == null){ // 如果左子树为空,则插入到左子树
lastParentNode.left = newNode;
} else if(lastParentNode.right == null){ // 如果右子树为空,则插入到右子树
lastParentNode.right = newNode;
}else{
Console.WriteLine("父节点错误,父节点左右子树都不为空,无法插入!");
return;
}

newNode.parent = lastParentNode;

Node opt = newNode;
// 以最小堆的方式插入节点,即父节点小于等于子节点
// 如果是以最大堆的方式插入,则父节点要大于等于子节点 只要将 <= 改为 >= 即可
while(opt != null && opt.parent != null && opt.data <= opt.parent.data){
int tmp = opt.data;
opt.data = opt.parent.data;
opt.parent.data = tmp;
opt = opt.parent;
}
}
}
}
// 运行刚才写的代码
using System;
using System.Collections.Generic;

class Program
{
static void Main(string[] args)
{
BinaryHeap bh = new BinaryHeap();
bh.Insert(1);
bh.Insert(9);
bh.Insert(22);
bh.Insert(17);
bh.Insert(11);
bh.Insert(33);
bh.Insert(27);
bh.Insert(21);
bh.Insert(19);
TreeAlgo.LevelOrderTraversal(bh.root);
}
}
// TreeAlgo 帮助类代码
using System;
using System.Collections.Generic;
public static class TreeAlgo {
// 层序遍历树,打印出的内容,括号里面是父节点的值
public static void LevelOrderTraversal(Node root){
if(root == null){
return;
}

Queue<Node> q = new Queue<Node>();
q.Enqueue(root);

while(q.Count > 0){
Node currNode = q.Dequeue();
string msg =string.Format("{0}({1}) ", currNode.data, currNode.parent != null?currNode.parent.data.ToString():"null");
Console.WriteLine(msg);
if(currNode.left != null){
q.Enqueue(currNode.left);
}

if(currNode.right != null){
q.Enqueue(currNode.right);
}
}
}

// 按层遍历,获取第 index 个节点
public static Node GetIndexOfNodeWithLevelOrder(Node root, int index){
if(root == null){
return null;
}

Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
int iIndex = 0;
Node targetNode = null;
while(q.Count > 0){
Node currNode = q.Dequeue();
if(iIndex == index){
targetNode = currNode;
break;
}

if(currNode.left != null){
q.Enqueue(currNode.left);
}

if(currNode.right != null){
q.Enqueue(currNode.right);
}

iIndex += 1;
}

return targetNode;
}

// 获取按层遍历时,最后一层的最后一个节点
public static Node GetLastNodeOfLevelOrder(Node root){
if(root == null){
return null;
}

Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
Node lastNode = null;
while(q.Count > 0){
lastNode = q.Dequeue();
if(lastNode.left != null){
q.Enqueue(lastNode.left);
}

if(lastNode.right != null){
q.Enqueue(lastNode.right);
}
}

return lastNode;
}

// 按层序遍历,只要任何一个节点左子对为空,或右子树为空,则为要找的点(前提是这棵树必须为完全二叉树)
public static Node FindParentOfFartestLeftLocation(Node root){
if(root == null){
return null;
}

Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
Node targetNode = null;

while(q.Count > 0){
targetNode = q.Dequeue();
if(targetNode.left == null || targetNode.right == null){
break;
}

q.Enqueue(targetNode.left);
q.Enqueue(targetNode.right);
}

return targetNode;
}
}

上面的代码可以自己使用C#运行一下看结果。下面我们继续说删除节点的操作。

删除节点

删除节点,稍微复杂一点点,但也不是特别复杂,按下面的流程来操作即可

  1. 找到按层序遍历的最后一个节点,然后用最后一个节点的值,替换要删除节点的值。然后将最后一个节点值删除掉。看下面的图

p001906_Binary-Heap-6

p001907_Binary-Heap-7

p001908_Binary-Heap-8

上面的过程,我们已经将最后一个节点 21 替换到了要删除的节点 5 的位置,并且将原来 21 的节点从树中删除掉。但是现在的树不符合二叉堆的规则,所以我们需要浮动现在的 21 节点。

  1. 浮动节点,将树调整为正确的二叉堆。删除节点时,节点的浮动有可能需要往下浮动,也有可能需要往上浮动。我们当前所讲的,都是按最小堆来操作的。如果 21 节点比父节点小,则要往上浮动。如果 21 节点比父节点大,则要往下浮动。

往上浮动,只要循环判断是否比父节点小即可,就像插入节点那样。而往下浮动,可能面对着两个又节点,所以要选择和两个子节点中值小的那个节点进行数据交换。显然,现在的 21 节点需要往下浮动,浮动到没有子节点,或者没有比当前节点小的节点位置。

p001909_Binary-Heap-9

上图中,21 的子节点 9 和 11,需要和值更小的 9 进行交换

p001910_Binary-Heap-10

上图中,21 换到了原来 9 的位置,发现还有子节点,所以继续判断。因为 17 比 21 小,所以需要继续交换。

p001911_Binary-Heap-11

到此,发现没有更小的节点了,浮动完毕,整棵树符合二叉堆规则。

以上就是删除节点的流程,下面我们用代码去实现。下面是加入了删除函数的 BinaryHeap类

using System;

public class BinaryHeap {
public Node root;

public void Insert(int data){
Node lastParentNode = TreeAlgo.FindParentOfFartestLeftLocation(root);
if(lastParentNode == null){
Console.WriteLine("Insert Root Node " + data);
root = new Node(data);
}else{
Node newNode = new Node(data);
if(lastParentNode.left == null){ // 如果左子树为空,则插入到左子树
lastParentNode.left = newNode;
} else if(lastParentNode.right == null){ // 如果右子树为空,则插入到右子树
lastParentNode.right = newNode;
}else{
Console.WriteLine("父节点错误,父节点左右子树都不为空,无法插入!");
return;
}

newNode.parent = lastParentNode;

Node opt = newNode;
// 以最小堆的方式插入节点,即父节点小于等于子节点
// 如果是以最大堆的方式插入,则父节点要大于等于子节点 只要将 <= 改为 >= 即可
while(opt != null && opt.parent != null && opt.data <= opt.parent.data){
int tmp = opt.data;
opt.data = opt.parent.data;
opt.parent.data = tmp;
opt = opt.parent;
}
}
}

public void Delete(int index){
// 1. 找到要删除的节点
Node optNode = TreeAlgo.GetIndexOfNodeWithLevelOrder(root, index);

// 2. 按层序遍历,找到最后一层最后一个节点
Node lastNode = TreeAlgo.GetLastNodeOfLevelOrder(root);

// 3. 使用最后一个节点的数据替换掉要删除节点的数据
optNode.data = lastNode.data;

// 4. 把最后一层最后一个节点删除掉
if(lastNode.parent.left == lastNode){
lastNode.parent.left = null;
}else if(lastNode.parent.right == lastNode){
lastNode.parent.right = null;
}

// 5. 要删除的节点数据已经被替换,现在需要根据数据浮动到正确的位置
// 首先要判断是往下浮动还是往上浮动,因为我们是按最小堆操作的,
// 所以要先判断当前节点是否比父节点 "小",如果是,则要往上浮动,反之往下浮动
if(optNode.parent != null && optNode.data < optNode.parent.data){
while(optNode.parent != null && optNode.data < optNode.parent.data){
int tmp = optNode.data;
optNode.data = optNode.parent.data;
optNode.parent.data = tmp;

optNode = optNode.parent;
}
}
else{
// 尝试往下浮动
while(optNode.left != null || optNode.right != null){
Node compareNode = null;
if(optNode.left != null && optNode.right != null){
if(optNode.left.data < optNode.right.data){
compareNode = optNode.left;
}else{
compareNode = optNode.right;
}
}
else{
if(optNode.left != null){
compareNode = optNode.left;
}else if(optNode.right != null){
compareNode = optNode.right;
}
}

// 往下浮动,交换数据
if(compareNode != null && optNode.data > compareNode.data){
int temp = optNode.data;
optNode.data = compareNode.data;
compareNode.data = temp;
}

optNode = compareNode;
}
}

}
}

上面的代码中,删除函数的参数传的是第几个节点。当然,你也可以改成删除某个特定值的节点,删除逻辑都是一样的。

下面是运行的代码

using System;
using System.Collections.Generic;

class Program
{
static void Main(string[] args)
{
BinaryHeap bh = new BinaryHeap();
bh.Insert(1);
bh.Insert(5);
bh.Insert(6);
bh.Insert(9);
bh.Insert(11);
bh.Insert(8);
bh.Insert(15);
bh.Insert(17);
bh.Insert(21);

TreeAlgo.LevelOrderTraversal(bh.root);

bh.Delete(1);

Console.WriteLine("------ Delete 1");
TreeAlgo.LevelOrderTraversal(bh.root);
}
}

以上就是二叉堆插入和删除的逻辑。

Author: Moeif Studio

Permalink: http://blog.moeif.com/2019/12/30/data-structure-07-binary-heap/

任何技术问题,可加微信交流,微信: ifloop

搜索并关注微信公众号 [ 萌一小栈 ] 可及时订阅最新技术文章

Comments