算法导论第六章-堆排序（二）

6.2-1 直接上MAX-HEAPIFY的go语言实现：

package main

import (
    "fmt"
)

type heapify interface {
    LEFT(i int) int
    RIGHT(i int) int
    MaxHeapify(i int)
}

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 main() {
    a := maxHeap{27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0}
    var h heapify = a
    h.MaxHeapify(3)
    fmt.Println(h)
}

6.2-2 ：参考MAX-HEAPIFY，写出能够维护相应最小堆的MIN-HEAPIFY(A,i)的伪代码，并比较MIN-HEAPIFY与MAX-HEAPIFY的运行时间
答：与上题同理，运行时间相同，时间复杂度都为O(h),h为该堆的高度。

6.2-3 ：当元素A[i]比其他孩子的值都大时，调用MAX-HEAPIFY(A,i)会有什么结果？
答：不执行递归，原数组不变。

6.2-4：当i>A.heap-size/2时，调用MAX-HEAPIFY会有什么结果？
答：原数组不变。因为此时为叶结点。

6.2-5：试用循环控制结构取代递归，重写MAX-HEAPIFY的代码
golang实现：

package main

import (
    "fmt"
)

type heapify interface {
    LEFT(i int) int
    RIGHT(i int) int
    MaxHeapify(i int)
}

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) {
    for i <= len(A) {
        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]
            i = largest
        } else {
            return
        }
    }
}

func main() {
    a := maxHeap{27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0}
    var h heapify = a
    h.MaxHeapify(3)
    fmt.Println(h)
}

6.2-6 证明：对一个大小为n的堆，MAX-HEAPIFY的最坏情况运行时间为O(lgn)。
答：书p86已经给出了答案，不再赘述。

最后编辑于：2018.06.03 19:03:27