专栏首页网管叨bi叨關於用 Go 实现堆和堆操作,可能是最通俗易懂的讲解了

關於用 Go 实现堆和堆操作,可能是最通俗易懂的讲解了

堆是一种树形数据结构,分为大顶堆和小顶堆,顾名思义,大顶堆就是堆顶(第一个元素)始终存放的是这组元素中的最大元素,小顶堆就是堆顶元素是最小元素。如果需要从一组对象中查找最大值最小值,使用堆能够高效率的完成需求。

排序算法中的堆排序正是利用了堆这一数据完成的排序,堆在实际应用中主要被用于实现优先队列(priority queue)下面我们以小顶堆为例学习一下堆的结构和常规操作。

堆的特性

小顶堆

如上图所示,就是一个小顶堆,我们先来说说它的特性。

完全二叉树

首先堆是一棵完全二叉树,关于完全二叉树和满二叉树:

如果一个二叉树的任何节点,要么是叶子节点,要么左右子树均非空,则这棵二叉树称做满二叉树(full binary tree) 如果一个二叉树最多只有最下面的两层节点度数可以小于2,并且最下面一层的节点都集中在该层最左边的连续位置上,则此二叉树称做完全二叉树(complete binary tree)

满二叉树和完全二叉树

节点的规则

在小顶堆中存储数据时必须遵守这样一条规则 :堆中所有节点的值均不大于其左右子节点的值,一个节点与其兄弟节点之间没有必然的联系。

而在二叉查找树中是,左子 < 父 < 右子

存储结构

由于堆是一棵完全二叉树,可以用数组来存储,只需要通过简单的代数表达式,就能计算出要某个节点的父节点和子节点的索引位置,既避免了像链表那样使用指针来保持结构,又能高效的执行相应操作。

关于节点的父节点和子节点在堆中的位置需要记住下面三个公式:

  • 节点 i 的左子节点为2 * i + 1,右子节点为 2 * i+2
  • 节点 i 的父节点为 (i - 1) /2

C在数组中索引为2,左子为 2*2+1=5,右子为 2*2+2=6

用 Go 实现堆操作

上面我们分析完堆的特性和存储结构后,我们自己用 Go 语言实现一个堆以及堆的各种操作。

数据结构

type Heap []int

// 交换两个节点的值
func (h Heap) swap(i, j int) {
 h[i], h[j] = h[j], h[i]
}

// 比较两个节点的值
func (h Heap) less(i, j int) bool {
  // 如果实现的是大顶堆,修改这里的判断即可
 return h[i] < h[j]
}

上面我们定义了小顶堆的数据结构以及它的两个基本操作,比较以及交换两个节点的值。下面来实现堆结构上的常规操作。

插入

向堆中插入数据时,首先会把元素放到末尾。如下图所示,向小顶堆中插入一个值为 5 的节点

向堆中插入一个新节点

先把节点放到了堆的末尾

先插入到堆的末尾

末尾插入新节点后,不再满足小顶堆的要求,故需要沿着其路径,自下而上依次比较和交换该节点与父节点的位置,直到重新满足小顶堆的性质为止。

5>6,不满足父节点必须小于等于子节点的性质,交换之

交换位置后,再比较发现比父节点大了,停止交换

如上图所示,首先,新添加的节点加入到末尾。为了保持小顶堆的性质,需要让该节点沿着其路径,自下而上依次比较和交换自身与父节点点的位置,直到重新满足小顶堆的性质为止。

这样会出现两种情况,要么新节点一直升到堆顶,要么到某一位置时发现父节点比自己小,则停止。

上面的流程代码如下:

func (h Heap) up(i int) {
 for {
  f := (i - 1) / 2 // 父节点在数组中的位置
  if i == f || h.less(f, i) {
   break
  }
  h.swap(f, i)
  i = f
 }
}

// 注意go中所有参数都是值传递
// 所以要让h的变化在函数外也起作用,此处要传指针
func (h *Heap) Push(x int) {
 *h = append(*h, x)
 h.up(len(*h) - 1)
}

删除

从最小堆中删除节点,分为以下三个步骤

  • 把最末端的节点和要删除节点的位置进行交换。
  • 删除末端节点
  • 原来的末端节点需要与新位置上的父节点做比较,如果小于要做 up(看上面的方法),如果大于父节点,则再和子节点做比较,即 down 操作,直到该节点下降到小于最小子节点为止。

与子节点进行比较交换的 down 操作的流程用代码表示为:

func (h Heap) down(i int) {
 for {
  l := 2*i + 1 // 左孩子
  r := 2*i +2 // 右孩子
  if l >= len(h) {
   break // i 已经是叶子节点,退出操作。
  }
  j := l
  if r < len(h) && h.less(r, l) {
   j = r // 右孩子为最小子节点
  }
  // i 与最小子节点进行比较 
  if h.less(i, j) {
   break // 如果父节点比子节点小,则不交换
  }
  h.swap(i, j) // 交换父子节点
  i = j        //继续向下比较
 }
}

实现了核心的up down 操作后,堆的Remove操作便很简单,代码如下:

// 删除堆中位置为i的元素
// 返回被删元素的值
func (h *Heap) Remove(i int) (int, bool) {
 if i < 0 || i > len(*h)-1 {
  return 0, false
 }
 n := len(*h) - 1
 h.swap(i, n) // 用最后的元素值替换被删除元素
 // 删除最后的元素
 x := (*h)[n]
 *h = (*h)[0:n]
 // 如果当前元素大于父节点,向下筛选
 if i == 0 || (*h)[i] > (*h)[(i-1)/2] {
  h.down(i)
 } else { // 当前元素小于父节点,向上筛选
  h.up(i)
 }
 return x, true
}

弹出堆顶元素

弹出堆顶元素,就是删除 i = 0 的节点。

// 弹出堆顶的元素,并返回其值
func (h *Heap) Pop() int {
  x, _ := h.Remove(0)
  return x
}

建堆

讲完了堆的核心操作 updown 后,我们来看一下如何根据一个数组构造一个小顶堆。

建立堆的过程就是完全二叉树,从下到上调整堆的过程,从 i = len(arr) /2 开始依次向上调整,i = len(arr) /2是堆中末尾节点的父节点, i=0是根节点。

func BuildHeap(arr []int) Heap {
 h := Heap(arr)
 n := len(h)
  // 从第一个非叶子节点,到根节点
  for i := n/2 - 1; i >= 0; i-- {
  h.down(i)
 }

 return h
}

堆排序

学完堆的基础知识后,我们再来看堆排序就变得非常简单。利用最小堆的特性,我们每次都从堆顶弹出一个元素(这个元素就是当前堆中的最小值),即可实现升序排序。代码如下:

func HeapSort(arr []int) {
  // 创建堆
 heap := BuildHeap(arr)
 var sortedArr []int
 for len(heap) > 0 {
  sortedArr = append(sortedArr, heap.Pop())
 }

 fmt.Println(sortedArr)
}

func main() {
 //输出 [3 8 10 15 15 16 17 19 24 30 33]
  HeapSort([]int{33, 24, 8, 3, 10, 15, 16, 15, 30, 17, 19}) 
}
  

Go 标准库对堆的定义

堆是一种很好的实现优先队列的数据结构,我们在这里自己实现了一个小顶堆。Go 在它的标准库 container/heap 也提供了堆的定义,

type Interface interface {
 sort.Interface
 Push(x any) // add x as element Len()
 Pop() any   // remove and return element Len() - 1.
}

它匿名嵌套的 sort.Interface 的定义如下:

type Interface interface {
 // Len is the number of elements in the collection.
 Len() int
 // Less reports whether the element with
 // index i should sort before the element with index j.
 Less(i, j int) bool
 // Swap swaps the elements with indexes i and j.
 Swap(i, j int)
}

也就是说,我们要使用go标准库给我们提供的heap,那么必须自己实现上面两个接口定义的方法,这些方法的实现方式就是我们上面演示的建堆、插入、删除这些操作,这里就不再继续演示 Go 这个 heap 库的使用啦。

参考

  • 图例来自《我的第一本算法书》
  • https://www.cnblogs.com/yahuian/p/go-heap.html

- END -

文章分享自微信公众号:
网管叨bi叨

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

作者:KevinYan11
原始发表时间:2022-04-18
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 全面迎接.Net3.0时代的到来(WCF/WF/WPF/LINQ)

    全面迎接.Net3.0时代的到来(WCF/WF/WPF/LINQ) .Net3.0从2006年发布预览版到今天(最高版本已经达到.Net3.5了),已经日趋稳...

    菩提树下的杨过
  • Java 虚拟机圖文詳解: JVM 體系結構 ( The JVM Architecture Explained

    A Virtual Machine is a software implementation of a physical machine. Java was d...

    一个会写诗的程序员
  • Java面试系列2

    六、&和&&的区别? &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and) 七、swtich是否能作用在byte上,是否能作用在long上,是否...

    Java帮帮
  • 走进Golang之运行与Plan9汇编

    通过上一篇走进Golang之汇编原理,我们知道了目标代码的生成经历了那些过程。今天我们一起来学习一下生成的目标代码如何在计算机上执行。以及通过查阅 Golang...

    大愚
  • 深入理解计算机系统(1.3)------操作系统的抽象概念

      上一篇博客我们讲解了存储设备的层次结构,并详细讲解了高速缓存的原理,以及可以利用高速缓存来提高程序性能。如果对Java Web 熟悉的,我们可以理解高速缓存...

    IT可乐
  • Jvm性能监控工具<深入了解jvm读书笔记>

    了解了部分JVM运行的原理之后,就要进入实战环节啦.在实际工作中,我们既不需要去实现虚拟机,也不需要对垃圾收集或者内存分配过程进行DEBUG.但是我们经常需要对...

    呼延十
  • JVM-内存结构「建议收藏」

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net

    全栈程序员站长
  • 逆向 Framework.jar

    Ref:http://www.addictivetips.com/mobile/what-is-odex-and-deodex-in-android-compl...

    全栈程序员站长
  • 【编程入门】C语言堆栈入门——堆和栈的区别

    在计算机领域,堆栈是一个不容忽视的概念,我们编写的C语言程序基本上都要用到。但对于很多的初学着来说,堆栈是一个很模糊的概念。堆栈:一种数据结构、一个在程序运行时...

    程序员互动联盟
  • Golang之变量去哪儿

    写过C/C++的同学都知道,调用著名的malloc和new函数可以在堆上分配一块内存,这块内存的使用和销毁的责任都在程序员。一不小心,就会发生内存泄露,搞得胆战...

    梦醒人间
  • Golang之变量去哪儿

    写过C/C++的同学都知道,调用著名的malloc和new函数可以在堆上分配一块内存,这块内存的使用和销毁的责任都在程序员。一不小心,就会发生内存泄露,搞得胆战...

    李海彬
  • 从零开始学TensorFlow【什么是TensorFlow?】

    TensorFlow是什么意思?Tensor?Flow?这篇文章介绍TensorFlow一些最基础的知识。

    Java3y
  • Go内存管理-上篇

    本主题文章讲Go内存分配管理,分为上篇和下篇两篇文章,上篇主要讲内存分配相关概念和tcmalloc原理,下篇将具体介绍Go内存分配原理。这是上篇部分,核心内容在...

    数据小冰
  • Nacos源码中为什么使用了String.intern方法?

    面试的时候经常被问到String的intern方法的调用及内存结构发生的变化。但在实际生产中真正用到过了吗,看到过别人如何使用了吗?

    程序新视界
  • 机器学习面试

    线性回归的因变量是连续变量,自变量可以是连续变量,也可以是分类变量。如果只有一个自变量,且只有两类,那这个回归就等同于t检验。如果只有一个自变量,且有三类或更多...

    用户2909867

扫码关注腾讯云开发者

领取腾讯云代金券