侧边栏壁纸
  • 累计撰写 16 篇文章
  • 累计创建 17 个标签
  • 累计收到 1 条评论

二叉堆

xiuxiubiu
2020-08-01 / 0 评论 / 0 点赞 / 807 阅读 / 3,360 字 / 正在检测是否收录...

完全二叉树

完全二叉树(complete binary tree)有一个重要的特点,给定任意一个结点,可以根据其编号直接快速计算出其父节点和子结点的编号。这使得二叉树可以方便的存储到数组中,数组中的元素索引正好对应结点的编号,树中的父子关系可以通过索引关系维持,不需要单独保存。如下图,假定编号从0开始:
completebinarytreearray.png

若编号为i,则父节点编号为(i-1)/2,左子结点编号为2i+1,右子结点编号为2i+2。比如:索引为4的元素E,其父结点是(4-1)/2,也就是索引为1的元素B,左子结点是2*4+1,也就是索引为9的元素J,右子结点是2*4+2,也就是索引为10的元素K


二叉堆概念

二叉堆(bianry heap)是一种特殊的堆(heap),逻辑上是一种完全二叉树(complete binary tree),物理存储上使用数组,堆中可以有重复的元素,元素间不是完全有序的,但对于父子结点间,有一定的顺序要求,根据顺序要求分为两种类型:

  • 父结点的键值总是小于或等于任何一个子结点的键值,叫做最小堆(min heap),又称小根堆。
  • 父结点的键值总是大于或等于任何一个子结点的键值,叫做最大堆(max heap),又称大根堆。
    heap.png

堆的构造

首先将初始的关键字序列按层次次序存放到用一维数组表示的一颗完全二叉树的各个结点之中,这里的完全二叉树一般来说还不是堆。假设结点数为n,显然所有的0(n-2)/2的结点都是非叶子结点,然后把以非叶子结点为根的子树都排列成堆,就完成了堆的构建。
heapcreate.png
使用上图的关键字集合构造最小堆,则:
k = {35, 26, 64, 10, 59, 48, 17, 23, 45, 31}

  • k的关键字个数为10,所以从(10 -2) / 2,也就是索引为4的关键字59开始处理。
  • 父节点索引为4,则左子结点索引为2*4+1,也就是9,右子结点为2*4+2,也就是10,因为索引10不存在,所以只存在索引为9的左子结点31
  • 比较父节点和左右子结点中较小的值,若父结点较大大,则交换其位置,比如图(a):右子结点不存在,则最小的值为左子结点3159 > 31,则将索引为4的关键字改为31
  • 判断值改变后的子结点是否满足堆的定义,若满足则处理下一个非叶子结点,如图(b)(c)。若不满足堆的定义,则对此结点重复上一步,直到满足堆的定义,如图(d)。
  • 依次将其余的非叶子结点,重复上面的流程,最后就得到一个最小堆。
func genBinaryHeap(arr []int) []int {
	
	length := len(arr)
	
	// 从最后一个非叶子结点开始往前挨个构建堆
	for start := (length - 2) / 2; start >= 0; start-- {
		
		// 左子结点索引
		left := 2*start + 1
		
		// 若左子结点不存在
		// 则右子结点也不存在
		// 此结点为叶子结点
		for left < length {
			
			// 右子结点索引
			right := 2*start + 2
			
			// 假设left较小
			min := left
			
			// 若右子结点存在且左子结点大于右子结点
			// 最小值的索引改为右结点
			if right < length && arr[left] > arr[right] {
				min = right
			}
			
			// 如果当前结点小于所有子结点
			// 则以此结点为根的树已是堆
			// 跳出循环
			if arr[start] <= arr[min] {
				break
			}
			
			// 如果当前结点大于最小的子结点
			// 交换两个结点的值
			if arr[start] > arr[min] {
				tmp := arr[start]
				arr[start] = arr[min]
				arr[min] = tmp
			}
			
			// 将start设置为被交换的最小子结点
			// 设置左子结点为此子结点的左子结点
			// 继续将被交换的子结点为根的树构建为堆
			start = min
			left = 2*start + 1
		}
		
	}
	
	return arr
}

堆的添加

每次将新结点总是添加已建成的最小堆后面,由于新结点的加入,可能会破坏堆的性质,因此需要从下向上调整使它所在的子树成为堆。
如图(a),添加一个15的结点:

  • 15添加到堆最后面
  • 比较15与其父结点31的大小,15 < 31交换其位置
  • 找到交换位置后15的父结点,重复上一步
  • 直到此结点大于等于父节点,或者此结点成为堆的根结点

heapadd.png

func binaryHeapAdd(heap []int, node int) []int {

	// 新结点添加到堆最后
	heap = append(heap, node)

	// 新结点索引
	index := len(heap) - 1

	// 索引为0则为堆的根结点
	for index > 0 {

		// 新结点所在树的根结点
		root := (index - 1) / 2

		// 若新结点大于或等于根结点
		// 新结点所在的树已经是堆
		if heap[index] >= heap[root] {
			break
		}

		// 如果新结点小于根结点交换位置
		if heap[index] < heap[root] {
			tmp := heap[root]
			heap[root] = heap[index]
			heap[index] = tmp
		}

		// 更新新结点的位置为所在树的根结点位置
		index = root
	}

	return heap
}

堆的删除

删除一般是在堆顶进行,把堆顶元素删除后,再把堆尾的元素移动到堆顶。由于用堆尾元素取代堆顶可能会破坏堆的性质,因此需要从上到下进行调整。

  • 删除堆顶的元素10,图(a)
  • 将堆尾元素31移动到堆顶,图(b)
  • 将堆顶元素从上到下依次调整子树为堆,图(c)

heapdel.png

func binaryHeapDelete(heap []int) []int {

	// 堆尾元素移动到堆顶
	heap[0] = heap[len(heap)-1]

	// 删除堆尾元素
	heap = heap[:len(heap)-1]

	// 最后一个非叶子结点索引
	index := (len(heap) - 1) / 2

	// 堆顶元素当前索引
	root := 0

	for root <= index {

		// 左右子结点索引
		left := 2*root + 1
		right := 2*root + 2

		// 假设左子结点小于右子结点
		min := left

		// 若左子结点大于右子结点
		// 最小结点改为右子结点
		if right < len(heap) && heap[left] > heap[right] {
			min = right
		}

		// 当前结点小于等于最小子结点
		// 当前结点为根的子树已经是堆
		// 退出循环
		if heap[root] <= heap[min] {
			break
		}

		// 当前结点大于最小子结点相互交换位置
		if heap[root] > heap[min] {
			tmp := heap[min]
			heap[min] = heap[root]
			heap[root] = tmp
		}

		// 更新当前结点为最小子结点
		// 继续调整以最小子结点为根的子树为堆
		root = min
	}
	return heap
}

运行代码

package main

import "fmt"

func main() {
	k := []int{35, 26, 64, 10, 59, 48, 17, 23, 45, 31}
	heap := genBinaryHeap(k)
	fmt.Println(heap)
	addHeap := binaryHeapAdd(heap, 15)
	fmt.Println(addHeap)
	delHeap := binaryHeapDelete(addHeap)
	fmt.Println(delHeap)
}

解决的问题

  • 优先级队列。顺序队列很多时候是无法满足需求的,现实中经常需要按优先级来处理队列任务,每次处理当前优先级最高的任务,即使添加较晚,也应该被优先处理。
  • 求前K个最大的元素,元素个数不确定,数据量可能很大,甚至数据源源不断的添加。这种情况可以维护一个最小堆,每次有新数据和堆顶元素比较,如果大于堆顶元素,删除堆顶元素,将新元素放到堆顶,然后从上到下调整为最小堆。
  • 求排序后中间的你那个元素的值,同样数据可能很大,甚至源源不断的添加。这种情况同时维护最大堆和最小堆,假设中值是m,则在最大堆中维护小于m的值,在最小堆中维护大于m的值。每当有新元素到达,首先和m做比较,如果等于m则抛弃,如果大于m则添加到最小堆,如果小于m则添加到最大堆,然后比较两个堆的元素个数,如果两个堆的元素个数查大于等于2,则将m添加到元素个数较小的堆,然后将元素个数较多的堆的根结点移出作为中值m。
0

评论