6.5-1~6.5-5:略 可以参考最小优先队列的golang实现
6.5-6 在HEAP-INCREASE-KEY的第五行的交换操作中，一般需要通过三次赋值来完成。想一想如何利用INSERTTION-SORT内循环部分的思想，只用一次赋值就完成这一交换操作？
答：伪代码如下
while i >1 and A[PARENT(i)] < key
A[i] = A[PARENT(i)]
i = PARENT(i)
end while
A[i] = key
6.5-7 试说明如何利用优先队列来实现一个先进先出队列，以及如何使用优先队列来实现栈。
答：栈的定义: 栈。
实现：在优先队列的数据结构中增加个count的字段，这个字段表示的是当前这个队列里面的元素个数。然后每次添加新元素的时候，用这个count值来表示它的key，这样就能实现先进后出了。
6.5-8 HEAP-DELETE(A,i)操作能够将结点i从堆A中删除。对于一个包含n个元素的堆，请设计一个能够在O(lgn)时间内完成的HEAP-DELETE操作
答:伪代码:
A[i] = A[A.heapSize]
A.heapSize = A.heapSize -1
MAX-HEAPIFY(A,i)
6.5-9 请设计一个时间复杂度为O(nlgk)的算法，它能够将k个有序链表合并为一个有序链表，这里n是所有输入链表包含的总的元素个数。
答:这里要分为三大部分，第一部分是单链表的golang实现，代码为
package main
import (
"errors"
"fmt"
)
//Element 定义元素类型
type Element int
//LinkNode 定义结点
type LinkNode struct {
Data Element
Next *LinkNode
}
//LinkNodeInterface 函数接口
type LinkNodeInterface interface {
Add(data Element) //后面添加
Delete(index int) (Element, error) //删除指定index位置元素
Insert(index int, data Element) error //在指定index位置插入元素
GetLength() int //获取长度
Search(data Element) int //查询元素的位置
GetData(index int) (Element, error) //获取指定index位置的元素
}
//GetLength 获取长度
func (head *LinkNode) GetLength() int {
return int(head.Data)
}
//Add 添加数据
func (head *LinkNode) Add(data Element) {
point := head
for point.Next != nil {
point = point.Next
}
node := new(LinkNode)
node.Data = data
point.Next = node
head.Data++
}
//Delete 删除结点
func (head *LinkNode) Delete(index int) (Element, error) {
if index < 0 || index >= head.GetLength() {
return 0, errors.New("please check index")
}
point := head
for i := 0; i < index; i++ {
point = point.Next
}
data := point.Next.Data
point.Next = point.Next.Next
head.Data--
return data, nil
}
//Insert 插入
func (head *LinkNode) Insert(index int, data Element) error {
//检验index合法性
if index < 0 || index >= head.GetLength() {
return errors.New("please check index")
}
point := head
for i := 0; i < index; i++ {
point = point.Next
}
node := new(LinkNode)
node.Data = data
node.Next = point.Next
point.Next = node
head.Data++
return nil
}
//Search 搜索 -1表示不存在该元素
func (head *LinkNode) Search(data Element) int {
point := head.Next
index := 0
for point != nil {
if point.Data == data {
fmt.Println(data, "exist at", index, "th")
return index
}
index++
point = point.Next
}
return -1
}
//GetData 获取data
func (head *LinkNode) GetData(index int) (Element, error) {
point := head
if index < 0 || index >= head.GetLength() {
return 0, errors.New("please check index")
}
for i := 0; i <= index; i++ {
point = point.Next
}
return point.Data, nil
}
//Traverse 遍历
func (head *LinkNode) Traverse() {
point := head
for point.Next != nil {
point = point.Next
fmt.Println(point.Data)
}
fmt.Println("Traverse OK!")
}
然后是针对链表改造过的最小堆，原来的最小堆只是简单的针对整数的。
package main
// MinHeap 最小堆的结构
type MinHeap struct {
heapSize int
heap []*LinkNode
}
// LEFT 返回子树左边的元素
func (A *MinHeap) LEFT(i int) int {
return i << 1
}
// RIGHT 返回子树右边的元素
func (A *MinHeap) RIGHT(i int) int {
return (i<<1 + 1)
}
// PARENT 返回父结点
func (A *MinHeap) PARENT(i int) int {
return i >> 1
}
// MinHeapify 最小化堆
func (A *MinHeap) MinHeapify(i int) {
smallest := i
l := A.LEFT(i + 1)
r := A.RIGHT(i + 1)
if l <= A.heapSize && A.heap[l-1].Data < A.heap[i].Data {
smallest = l - 1
}
if r <= A.heapSize && A.heap[r-1].Data < A.heap[smallest].Data {
smallest = r - 1
}
if smallest != i {
A.heap[smallest], A.heap[i] = A.heap[i], A.heap[smallest]
A.MinHeapify(smallest)
}
}
// BuildMinHeap 构建最小堆
func (A *MinHeap) BuildMinHeap() {
for i := A.heapSize / 2; i >= 0; i-- {
A.MinHeapify(i)
}
}
// GetHeapSize 获得堆大小
func (A *MinHeap) GetHeapSize() int {
return A.heapSize
}
// AlterHeapSize 更改堆大小
func (A *MinHeap) AlterHeapSize(i int) {
A.heapSize = i
}
// GetElement 获得堆中的元素
func (A *MinHeap) GetElement(i int) *LinkNode {
return A.heap[i]
}
// SetElement 更新堆中的元素
func (A *MinHeap) SetElement(i int, key *LinkNode) {
A.heap[i] = key
}
// Swap 交换堆中的元素
func (A *MinHeap) Swap(i int, j int) {
A.heap[i], A.heap[j] = A.heap[j], A.heap[i]
}
// Append 向堆中追加元素
func (A *MinHeap) Append(i *LinkNode) {
A.heap = append(A.heap, i)
}
// NewMinHeap 最小里堆的构造函数
func NewMinHeap(heapSize int, a []*LinkNode) *MinHeap {
minHeap := MinHeap{heapSize: heapSize, heap: a}
minHeap.BuildMinHeap()
return &minHeap
}
第三部分就是K路归并算法了,思想是将每个链表的第一个元素提取出来，初始化成一个最小堆，然后取出该最小堆中的第一个元素就是根节点，该节点的data便是最小的，然后将该节点插入到新的单链表中；插入完成后，这个根节点所在的链表的下一个元素，将该元素替代原来根节点在最小堆中的位置然后最小堆化根节点，然后取新最小化的最小堆的根节点，插入到新的链表中。如果某个链表取完后，则将最小堆的第一个元素和最后一个元素对换一下，再最小堆化一下，同时堆的大小减1；最后，当最小堆的大小为0时，新的归并后的链表也就完成了。
时间复杂度：因为有k个链表，总共有n个元素，因此发生了n次的最小堆化，时间复杂度为O(nlgk)
//KMerge K路归并算法：linkedListArr单链表的slice
func KMerge(linkedListArr []*LinkNode) *LinkNode {
//l 是最后生成那个单链表
l := LinkNode{Data: 0, Next: nil}
//先把k个链表的第一个元素初始化成一个最小堆
a := NewMinHeap(len(linkedListArr), linkedListArr)
for a.GetHeapSize() > 0 {
//最小堆的第一个元素肯定是最小的元素
linkNode := a.heap[0]
//fmt.Println(linkNode.Data)
l.Add(linkNode.Data)
if linkNode.Next != nil {
//如果最小堆根元素的NEXT不为空，则用该链表下一个元素去替代根元素然后最小化堆
a.SetElement(0, linkNode.Next)
a.MinHeapify(0)
} else {
//如果NEXT为空指针，则将最小堆的最后一个叶节点和根节点交换，然后最小化堆的第一个
a.heap[0], a.heap[a.GetHeapSize()-1] = a.heap[a.GetHeapSize()-1], a.heap[0]
a.AlterHeapSize(a.GetHeapSize() - 1)
a.MinHeapify(0)
}
}
return &l
}
测试以及结果:
//第一个单链表
a := LinkNode{Data: 0, Next: nil}
a.Add(1)
a.Add(4)
a.Add(9)
//第二个单链表
b := LinkNode{Data: 0, Next: nil}
b.Add(2)
b.Add(3)
b.Add(7)
//第三个单链表
c := LinkNode{Data: 0, Next: nil}
c.Add(6)
c.Add(8)
c.Add(10)
KMerge([]*LinkNode{a.Next, b.Next, c.Next}).Traverse()
1
2
3
4
6
7
8
9
10
Traverse OK!
思考题部分
6.1 我们可以通过反复调用MAX-HEAP-INSERT实现向一个堆中插入元素，考虑BUILD-MAX-HEAP的如下实现方式：
BUILD-MAX-HEAP'(A)
A.heap-size = 1
for i = 2 to A.length
MAX-HEAP-INSERT(A,A[i])
a.当输入数据相同的时候，BUILD-MAX-HEAP和BUILD-MAX-HEAP'生成的堆是否总是一样？如果是，请证明；否则，请举出一个反例。
b.证明：在最坏的情况下，调用BUILD-MAX-HEAP'建立一个包含n个元素的堆的时间复杂度是O(nlgn)
答: a. 不是总是一样的。叶节点顺序会不同。反例：对于一个数组A{3,2,1,4,5},当我们运行BUILD-MAX-HEAP'时得到5，4，1，2，3；当我们运行BUILD-MAX-HEAP时，得到5，4，1，3，2
b.每次插入花费最多O(lgn),共有n次插入，所以时间复杂度为O(nlgn)
6-2 d叉堆与二叉堆很类似，但（一个可能的例外是）其中的每个非叶节点有d个孩子，而不是仅仅两个。
a.如何在一个数组中表示一个d叉堆
b.包含n个元素的d叉堆的高度是多少？请用n和d表示
c.请给出EXTRACT-MAX在d叉最大堆上的一个有效实现，并用d和n表示出它的时间复杂度。
d.给出INSERT在d叉最大堆的一个有效实现，并用d和n表示出它的时间复杂度。
e.给出INCREASE-KEY(A,i,k)的一个有效实现,并用d和n表示出它的时间复杂度。
答:a. PAARENT[i] = math.Floor((i+1)/d) child(k,i) = (i - 1) * d + 1 + k 其中i代表数组第i个元素，k表示第k个子元素
b.高度是math.floor(logd(n*(d-1)))
c.伪代码:
//EXTRACT-MAX
if A.heap-size <1 then
error "heap underflow"
end if
max = A[1]
A[1] = A[A.heap-size]
A.heap-size --
DMAX-HEAPIFY(A,1)
//DMAX-HEAPIFY(A,i)
largest = i
for k = 1 to d do
if CHILD(k,i) <= A.heap-size and A[CHILD(k,i) > A[i] then
largest = CHILD(k,i)
end if
end for
if largest != i then
exchange A[i] with A[largest]
DMAX-HEAPIFY(A,largest)
end if
其中DMAX-HEAPIFY(A,1)是一个不断迭代递归的过程，每一层都要和d个元素比较所以时间复杂度为dlogd(n)
d.伪代码为:
// INSERT
A.heap-size ++
A[A.heap-size] = key
i = A.heap-size
while i >1 and A[PARENT(i)] < A[i] do
exchange A[i] with A[PARENT(i)]
i = PARENT(i)
end while
时间复杂度为O(logd(n))
e:伪代码为:
if key < A[i] then
error "new key is smaller than current key"
end if
A[i] = key
while i >1 and A[PARENT(i)] < A[i] do
exchange A[i] with A[PARENT(i)]
i = PARENT(i)
end while
时间复杂度为O(logd(n))
