6.3-1说明BUILD-MAX-HEAP在数组A=[5,3,17,10,84,19,6,22,9]上的操作过程
答：废话不多说，直接上代码，这次在接口上添加了一个BuildMaxHeap函数，基于上一节的MaxHeapify函数，美滋滋。
package main
import (
"fmt"
)
type heapify interface {
LEFT(i int) int
RIGHT(i int) int
MaxHeapify(i int)
BuildMaxHeap()
}
type maxHeap []int
func (A maxHeap) LEFT(i int) int {
return i << 1
}
func (A maxHeap) RIGHT(i int) int {
return (i<<1 + 1)
}
func (A maxHeap) MaxHeapify(i int) {
largest := i
l := A.LEFT(i)
r := A.RIGHT(i)
if l <= len(A) && A[l-1] > A[i-1] {
largest = l
}
if r <= len(A) && A[r-1] > A[largest-1] {
largest = r
}
if largest != i {
A[largest-1], A[i-1] = A[i-1], A[largest-1]
A.MaxHeapify(largest)
}
}
func (A maxHeap) BuildMaxHeap() {
for i := len(A) / 2; i > 0; i-- {
A.MaxHeapify(i)
}
}
func main() {
a := maxHeap{5, 3, 17, 10, 84, 19, 6, 22, 9}
var h heapify = a
h.BuildMaxHeap()
fmt.Println(h)
}
打印出来的结果：[84 22 19 10 3 17 6 5 9]
对于BUILD-MAX-HEAP中第二行的循环控制变量i来说，为什么我们要求它是从[A.length/2]到1递减，而不是从1到[A.length/2]递增呢？
答：因为这样才能保证对于每个子堆的根元素，它的子堆是最大堆。
6.3-3 证明：对于任一包含n个元素的堆中，至多有[n/2^(h+1)]个高度为h的结点
答：利用数学归纳法。当h=0时，有n/2个结点，成立。
当h=k时，假设有[n/2^(k+1)]个高度为k的结点成立。
则当h=k+1时，对于一棵二叉树来说则有[n/2(k+1)]/2个结点，即[n/2(k+2)]个结点，结论成立。
6.4-1 说明HEAPSORT在数组A=[5,13,2,25,7,17,20,8,4]上的操作过程
答：老规矩：直接上代码。
package main
import (
"fmt"
)
type heapify interface {
LEFT(i int) int
RIGHT(i int) int
MaxHeapify(i int, heapSize int)
BuildMaxHeap()
HeapSort()
}
type maxHeap []int
func (A maxHeap) LEFT(i int) int {
return i << 1
}
func (A maxHeap) RIGHT(i int) int {
return (i<<1 + 1)
}
func (A maxHeap) MaxHeapify(i int, heapSize int) {
largest := i
l := A.LEFT(i)
r := A.RIGHT(i)
if l <= heapSize && A[l-1] > A[i-1] {
largest = l
}
if r <= heapSize && A[r-1] > A[largest-1] {
largest = r
}
if largest != i {
A[largest-1], A[i-1] = A[i-1], A[largest-1]
A.MaxHeapify(largest, heapSize)
}
}
func (A maxHeap) BuildMaxHeap() {
for i := len(A) / 2; i > 0; i-- {
A.MaxHeapify(i, len(A))
}
}
func (A maxHeap) HeapSort() {
A.BuildMaxHeap()
for i := len(A); i >= 1; i-- {
A[i-1], A[0] = A[0], A[i-1]
A.MaxHeapify(1, i-1)
}
}
func main() {
a := maxHeap{5, 13, 2, 25, 7, 17, 20, 8, 4}
var h heapify = a
h.HeapSort()
fmt.Println(h)
}
结果:[2 4 5 7 8 13 17 20 25]
6.4-3 对于一个按升序排列的包含n个元素的有序数组A来说，HEAPSORT的复杂度是多少？如果A是降序呢？
答：升序情况下：复杂度为nlgn，和最坏情况没有区别。
降序情况下：复杂度为依然为nlgn。
6.4-4 证明在最坏的情况下，HEAPSORT的时间复杂度是nlgn
答：每次调用BUILD-MAX-HEAP的时间复杂度是O(n)，而n-1次调用MAX-HEAPIFY，每次的时间复杂度是O(lgn)，所以总的来说时间复杂度为nlgn。
网友评论