6.3-1說明BUILD-MAX-HEAP在數(shù)組A=[5,3,17,10,84,19,6,22,9]上的操作過程
答：廢話不多說，直接上代碼，這次在接口上添加了一個BuildMaxHeap函數(shù)，基于上一節(jié)的MaxHeapify函數(shù)，美滋滋。

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)
}

打印出來的結(jié)果：[84 22 19 10 3 17 6 5 9]

對于BUILD-MAX-HEAP中第二行的循環(huán)控制變量i來說，為什么我們要求它是從[A.length/2]到1遞減，而不是從1到[A.length/2]遞增呢？
答：因為這樣才能保證對于每個子堆的根元素，它的子堆是最大堆。

6.3-3 證明：對于任一包含n個元素的堆中，至多有[n/2^(h+1)]個高度為h的結(jié)點
答：利用數(shù)學(xué)歸納法。當(dāng)h=0時，有n/2個結(jié)點，成立。
當(dāng)h=k時，假設(shè)有[n/2^(k+1)]個高度為k的結(jié)點成立。
則當(dāng)h=k+1時，對于一棵二叉樹來說則有[n/2^{(k+1)]/2個結(jié)點，即[n/2}(k+2)]個結(jié)點，結(jié)論成立。

6.4-1 說明HEAPSORT在數(shù)組A=[5,13,2,25,7,17,20,8,4]上的操作過程
答：老規(guī)矩：直接上代碼。

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)
}

結(jié)果:[2 4 5 7 8 13 17 20 25]

6.4-3 對于一個按升序排列的包含n個元素的有序數(shù)組A來說，HEAPSORT的復(fù)雜度是多少？如果A是降序呢？
答：升序情況下：復(fù)雜度為nlgn，和最壞情況沒有區(qū)別。
降序情況下：復(fù)雜度為依然為nlgn。

6.4-4 證明在最壞的情況下，HEAPSORT的時間復(fù)雜度是nlgn
答：每次調(diào)用BUILD-MAX-HEAP的時間復(fù)雜度是O(n)，而n-1次調(diào)用MAX-HEAPIFY，每次的時間復(fù)雜度是O(lgn)，所以總的來說時間復(fù)雜度為nlgn。