面试经典算法:优先队列,最大堆,堆排序,左偏树Golang实现

堆排序

使用优先队列-最小/最大堆可实现。

优先队列

优先队列是一种能完成以下任务的队列:插入一个数值,取出最小的数值(获取数值,并且删除)。优先队列可以用二叉树来实现,我们称这种为二叉堆。

最小堆

最小堆是二叉堆的一种,是一颗完全二叉树(一种平衡树), 其特点是父节点的键值总是小于或者等于子节点。

实现细节(两个操作):
push:向堆中插入数据时,首先在堆的末尾插入数据,然后不断向上提升,直到没有大小颠倒时。
pop:从堆中删除最小值时首先把最后一个值复制到根节点上,并且删除最后一个数值。然后不断向下交换, 直到没有大小颠倒为止。在向下交换过程中,如果有两个子儿子都小于自己,就选择较小的
插入时间复杂度O(logN),删除时间复杂度O(logN),两个二叉堆合并时间复杂性O(NlogN).

最大堆同理。可用此结构实现堆排序算法。

/*
 最小堆
*/
package main
import "fmt"
type Heap struct {
 Size int
 Elems []int
}
func NewHeap(MaxSize int) *Heap {
 h := new(Heap)
 h.Elems = make([]int, MaxSize, MaxSize)
 return h
}
func (h *Heap) Push(x int) {
 h.Size++
 // i是要插入节点的下标
 i := h.Size
 for {
 if i <= 0 {
 break
 }
 // parent为父亲节点的下标
 parent := (i - 1) / 2
 // 如果父亲节点小于等于插入的值,则说明大小没有跌倒,可以退出
 if h.Elems[parent] <= x {
 break
 }
 // 互换当前父亲节点与要插入的值
 h.Elems[i] = h.Elems[parent]
 i = parent
 }
 h.Elems[i] = x
}
func (h *Heap) Pop() int {
 if h.Size == 0 {
 return 0
 }
 // 取出根节点
 ret := h.Elems[0]
 // 将最后一个节点的值提到根节点上
 h.Size--
 x := h.Elems[h.Size]
 i := 0
 for {
 // a,b为左右两个子节点的下标
 a := 2*i + 1
 b := 2*i + 2
 // 没有左子树
 if a >= h.Size {
 break
 }
 // 有右子树,找两个子节点中较小的值
 if b < h.Size && h.Elems[b] < h.Elems[a] {
 a = b
 }
 // 父亲小直接退出
 if h.Elems[a] >= x {
 break
 }
 // 交换
 h.Elems[i] = h.Elems[a]
 i = a
 }
 h.Elems[i] = x
 return ret
}
func (h *Heap) Display() {
 fmt.Printf("Size:%d,Elems:%#v\n", h.Size, h.Elems[0:h.Size])
}
func main() {
 h := NewHeap(100)
 h.Display()
 h.Push(3)
 h.Push(6)
 h.Push(7)
 h.Push(27)
 h.Push(1)
 h.Push(2)
 h.Push(3)
 h.Display()
 fmt.Println(h.Pop())
 h.Display()
 fmt.Println(h.Pop())
 h.Display()
 fmt.Println(h.Pop())
 h.Display()
 fmt.Println(h.Pop())
 h.Display()
 fmt.Println(h.Pop())
 h.Display()
}

左偏树

最小堆/最大堆如果两个堆进行合并,时间复杂度较高,左偏树是可合并的二叉堆,首先满足所有的堆的性质,其外,各种操作时间复杂度都是O(logN)。

左偏树的树节点需要保存的信息有:
1.左右子树节点编号
2.此节点到有空子结点的最短距离len(空子节点的节点,就是子节点数不足2个的节点)
3.自身权值
左偏就是每个节点的左子节点的len不小于右子节点的len(但并不代表左子节点数一定不小于右子节点数),那么可知左偏树中一个节点的距离就是右儿子距离+1(或没有右儿子),且左右子树都是左偏树。
合并树A和树B的操作方法如下: 
1.如果A或B有一个是空树,返回另一个。 
2.如果A的优先级比B低,交换A,B。(确保左堆根节点小于右堆根节点) 
3.递归处理,将B和A的右子树合并。(B,Right(A)递归处理) 
4.如果合并过后A的右儿子距离大于A的左儿子,交换A的左右儿子。(确保左儿子距离大于右儿子) 
5.更新A的距离。

左偏树合并操作合并的是两棵左偏树,对于堆的插入,就是合并一棵树和一个节点,对于堆的删除,就是合并根的两棵子树。

/*
 左偏树
*/
package main
import (
 "fmt"
)
type LeftistHeap struct {
 Root *Node
}
type Node struct {
 Data int
 Distance int
 LeftChild *Node
 RightChild *Node
}
func New() *LeftistHeap {
 h := new(LeftistHeap)
 return h
}
func (n *Node) Dist() int {
 if n == nil {
 return -1 // 空节点距离为-1
 }
 return n.Distance
}
func (h *LeftistHeap) Push(data int) {
 newNode := new(Node)
 newNode.Data = data
 h.Root = h.Root.Merge(newNode)
}
func (h *LeftistHeap) Pop() int {
 if h.Root == nil {
 return -1 // pop完
 }
 data := h.Root.Data
 h.Root = h.Root.LeftChild.Merge(h.Root.RightChild)
 return data
}
// 合并两棵左偏树
func (A *Node) Merge(B *Node) *Node {
 // 一棵树为空返回另外一棵树
 if A == nil {
 return B
 }
 if B == nil {
 return A
 }
 leftHeap := A
 rightHeap := B
 // 使左堆做为合并后的根节点
 if A.Data > B.Data {
 leftHeap = B
 rightHeap = A
 }
 // 递归:左堆的右子树和右堆进行合并,作为左堆右子树
 leftHeap.RightChild = leftHeap.RightChild.Merge(rightHeap)
 // 树翻转左右,确保左儿子距离大于右子
 if leftHeap.RightChild.Dist() > leftHeap.LeftChild.Dist() {
 leftHeap.LeftChild, leftHeap.RightChild = leftHeap.RightChild, leftHeap.LeftChild
 }
 if leftHeap.RightChild == nil {
 leftHeap.Distance = 0
 } else {
 leftHeap.Distance = leftHeap.RightChild.Dist() + 1
 }
 return leftHeap
}
// 递归先序排序
func (n *Node) Display() {
 if n == nil {
 fmt.Println("null")
 return
 }
 fmt.Println(n.Data)
 fmt.Printf("Node:%d,Left child:", n.Data)
 if n.LeftChild != nil {
 n.LeftChild.Display()
 } else {
 fmt.Print("null")
 }
 fmt.Println()
 fmt.Printf("Node:%d,Right child:", n.Data)
 if n.RightChild != nil {
 n.RightChild.Display()
 } else {
 fmt.Print("null")
 }
 fmt.Println()
}
func (h *LeftistHeap) Display() {
 h.Root.Display()
}
func main() {
 n := New()
 n.Display()
 fmt.Println("---")
 n.Push(3)
 n.Push(1)
 n.Push(5)
 n.Push(8)
 n.Display()
 fmt.Println(n.Pop())
 fmt.Println(n.Pop())
 fmt.Println(n.Pop())
 fmt.Println(n.Pop())
 fmt.Println(n.Pop())
 fmt.Println(n.Pop())
}

转载请注明:http://www.lenggirl.com/algorithm/heap.html

本文来自:简书

感谢作者:aside section._1OhGeD

查看原文:面试经典算法:优先队列,最大堆,堆排序,左偏树Golang实现

• 编辑
• 预览