[数据结构与算法]加工并存储数据的数据结构-优先队列

数据结构指的是存储数据的方式。用不同的方式存储数据，可以对数据做不同的高效操作。

堆

堆分为小顶堆和大顶堆，顾名思义，最小/大的为根节点，每次Pop()操作可以获取根节点元素。

堆的操作的时间复杂度为O(logn)。

基于数组的堆实现（Go）

type heap struct {
	nums []int
	sz   int // 节点编号
}

func (h *heap) Push(x int) {
	// 节点的编号
	i := h.sz
	h.sz++
	for i > 0 {
		parent := (i - 1) / 2

		if h.nums[parent] <= x {
			break
		}

		h.nums[i] = h.nums[parent]
		i = parent
	}
	h.nums[i] = x
}

func (h *heap) Pop() int {
	ret := h.nums[0]
	h.sz--
	x := h.nums[h.sz]
	i := 0
	for i*2+1 < h.sz {
		a, b := i*2+1, i*2+2
		if b < h.sz && h.nums[b] < h.nums[a] {
			a = b
		}
		if h.nums[a] >= x {
			break
		}
		h.nums[i] = h.nums[a]
		i = a
	}
	h.nums[i] = x
	return ret
}

基于标准库的堆实现（Go）

type hp []int

func (h hp) Len() int { return len(h) }

// Less中，小于为小顶堆，大于为大顶堆
func (h hp) Less(i, j int) bool  { return h[i] < h[j] }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

func main() {
	h := hp{}
	heap.Init(&h)
	heap.Push(&h, 3)
	heap.Push(&h, 5)
	heap.Push(&h, 1)
	for len(h) > 0 {
		fmt.Printf("%v\n", heap.Pop(&h))
	}
}

可以运用优先队列解决的题目

例一：Expedition

思路：在到达加油站$i$时，等同于获得了在之后的任何时候都可以加$B_i$单位汽油的一次权利。为了加油次数最少，当燃料为0时，则选择加油量最大的加油站。

具体地说：

• 经过加油站时，往优先队列里加入$B_i$
• 当燃料空时，如果优先队列也空，则无法到达终点。否则取出优先队列中最大的元素加油。

简洁地说：每到一个加油站，就把油买下来放在你的车里，当你没有油了，就加最大的桶。到达终点时，问你加了多少桶。

package main

import (
	"container/heap"
	"fmt"
)

var N, L, P int
var A, B = []int{}, []int{}

func solve() {
	h := hp{}
	heap.Init(&h)
	ans, pos := 0, 0
	for i := 0; i < N; i++ {
		// 前进的距离
		d := A[i] - pos

		// 不断加油直到油量足够行驶到下一个加油站
		for P-d < 0 {
			if len(h) == 0 {
				fmt.Println(-1)
				return
			}
			P += heap.Pop(&h).(int)
			ans++
		}
		P -= d
		pos = A[i]
		heap.Push(&h, B[i])
	}
	fmt.Println(ans)
}

func main() {
	N, L, P = 4, 25, 10
	A = []int{10, 14, 20, 21}
	B = []int{10, 5, 2, 4}
	solve()
}

type hp []int

func (h hp) Less(i, j int) bool  { return h[i] > h[j] }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h hp) Len() int            { return len(h) }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(int)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

例二：Fence Repair

在这里插入图片描述

在贪心算法中，每次取出最短的两个木板，然后求和再放进去。因此，可以利用优先队列，每次取出两个最小的元素。

Go语言有逃逸机制分析，因此不用像C/C++、Java等语言一样，声明全局变量来减少内存的消耗。

package main

import (
	"container/heap"
	"fmt"
)

func main() {
	// N := 3
	L := []int{8, 5, 8}
	h := hp{}
	heap.Init(&h)
	for _, num := range L {
		heap.Push(&h, num)
	}
	ans := 0
	for len(h) > 1 {
		l1, l2 := heap.Pop(&h).(int), heap.Pop(&h).(int)
		ans += (l1 + l2)
		heap.Push(&h, l1+l2)
	}
	fmt.Println(ans)
}

type hp []int

func (h hp) Less(i, j int) bool  { return h[i] < h[j] }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h hp) Len() int            { return len(h) }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(int)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

Leetcode的练习题

1046:最后一块石头的重量