CLRS6 堆排序

2017-05-09 | 阅读：次

6.1 堆

堆排序的时间复杂度是O(nlgn),且是原址排序。
0 <= A.heap-size <= A.length

PARENT(i)
    return i//2

LEFT(i)
    return 2i

right(i)
    return 2i+1

在堆排序的好的实现中，这三个函数通常是以"宏"或者"内联函数"的方式实现的。

最大堆 A[PARENT(i)] >= A[i]
最小堆 A[PARENT(i)] <= A[i]
练习6.1-1 What are the minimum and maximum numbers of elements in a heap of height h?

最多2^(h+1)-1
最少2^h

练习6.1-2 Show that an n-element heap has height floor(lgn).

高度lgn的堆最少n个元素，最多2n-1个元素

练习6.1-3 Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.

This is the property of maximum heap.

练习6.1-4 Where in a max-heap might the smallest element reside, assuming that all elements are distinct?

leaf node

练习6.1-5 Is an array that is in sorted order a min-heap?

取决于数组递增还是递减。

练习6.1-6 Is the sequence [23, 17, 14, 6, 13, 10, 1, 5, 7, 12] a max-heap?

No.

练习6.1-7 Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by floor(n/2) + 1, floor(n/2) + 2, … , n.

可以说这是显而易见的么~

6.2 维护堆的性质

MAX-HEAPIFY

MAX-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l <= A.heap-size and A[l] > A[i]
        largest = l
    else lagest = i
    if r <= A.heap-size and A[r] > A[largest]
        largest = r
    if largest != i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A, largest)

时间复杂度为O(h)

练习6.2-1 Using Figure 6.2 as a model, illustrate the operation of MAX-HEAPIFY(A, 3) on the array A = 27,17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0.

逐级使节点符合性质。

练习6.2-2 Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN- HEAPIFY(A, i), which performs the corresponding manipulation on a min-heap. How does the running time of MIN-HEAPIFY compare to that of MAX-HEAPIFY?

MIN-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l <= A.heap-size and A[l] < A[i]
        smallest = l
    else smallest = i
    if r <= A.heap-size and A[r] < A[smallest]
        smallest = r
    if smallest != i
        exchange A[i] with A[smallest]
        MIN-HEAPIFY(A, smallest)

运行时间是一样的

练习6.2-3 What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than its children?

It will do nothing.

练习6.2-4 What is the effect of calling MAX-HEAPIFY(A, i) for i > heap-size[A]/2?

It will do nothing.

练习6.2-5 The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAX-HEAPIFY that uses an iterative control construct (a loop) instead of recursion.

MAX-HEAPIFY(A, i)
    while True
        l = LEFT(i)
        r = RIGHT(i)
        if l <= A.heap-size and A[l] > A[i]
            largest = l
        else lagest = i
        if r <= A.heap-size and A[r] > A[largest]
            largest = r
        if largest != i
            exchange A[i] with A[largest]
            i = largest
        else
            break

练习6.2-6 Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is Ω(lg n). (Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a path from the root down to a leaf.)

最坏情况就是递归高度次。

6.3 建堆

build max heap

BUILD-MAX-HEAP(A)
    A.heap-size = A.length
    for i = floor(A.length/2) down to 1
        MAX-HEAPIFY(A, i)

时间: O(n)

练习6.3-1 Using Figure 6.3 as a model, illustrate the operation of BUILD-MAX-HEAP on the array A = [5, 3, 17, 10, 84, 19, 6, 22, 9].

从10开始~

练习6.3-2 Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from floor(length[A]/2) to 1 rather than increase from 1 to floor(length[A]/2)?

不满足MAX-HEAPIFY条件。

练习6.3-3 Show that there are at most ceil(n/2^(h+1)) nodes of height h in any n-element heap.

......

6.4 堆排序算法

heap sort

HEAPSORT(A)
    BUILD-MAX-HEAP(A)
    for i = A.length downto 2
        exchange A[1] with A[i]
        A.heap-size -= 1
        MAX-HEAPIFY(A, 1)

O(lgn)

练习6.4-1 Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the array A = [5, 13, 2, 25, 7, 17, 20, 8, 4].

It's easy.

练习6.4-2 Argue the correctness of HEAPSORT using the following loop invariant: At the start of each iteration of the for loop of lines 2-5, the subarray A[1…i] is a max-heap containing the i smallest elements of A[1…n], and the subarray A[i + 1…n] contains the n - i largest elements of A[1…n], sorted.

It's easy too.

练习6.4-3 What is the running time of heapsort on an array A of length n that is already sorted in increasing order? What about decreasing order?

都是theta(nlgn)

练习6.4-4 Show that the worst-case running time of heapsort is Ω(n lg n).

It's easy three.

练习6.4-5 Show that when all elements are distinct, the best-case running time of heapsort is Ω(n lg n).

http://stackoverflow.com/questions/4589988/lower-bound-on-heapsort

6.5 优先队列

heap-maximum

HEAP-MAXIMUM(A)
    return A[1]

heap-extract-max

HEAP-EXTRACT-MAX(A)
    if A.heap-size < 1
        error "heap underflow"
    max = A[1]
    A[1] = A[A.heap-size]
    A.heap-size -= 1
    MAX-HEAPIFY(A, 1)
    return max

heap-increase-key

HEAP-INCREASE-KEY(A, i, key)
    if key < A[i]
        error "new key is smaller than current key"
    A[i] = key
    while i > 1 and A[PARENT(i)] < A[i]
        exchange A[i] with A[PARENT(I)]
        i = PARENT(i)

max-heap-insert

MAX-HEAP-INSERT(A, key)
    A.heap-size += 1
    A[A.heap-size] = -INFINITE
    HEAP-INCREASE-KEY(A, A.heap-size, key)

所有优先队列的操作都可以在O(lgn)时间内完成
练习6.5-1 Illustrate the operation of HEAP-EXTRACT-MAX on the heap A = [15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1].

把15和1交换，然后max-heapify。

练习6.5-2 Illustrate the operation of MAX-HEAP-INSERT(A, 10) on the heap A = [15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1]. Use the heap of Figure 6.5 as a model for the HEAP-INCREASE-KEY call.

插入最后一个，然后heap-increase-key,不断与父元素比较并交换。

练习6.5-3 Write pseudocode for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.

HEAP-MINUMUM(A)
    return A[1]

HEAP-EXTRACT-MIN(A)
    if A.heap-size < 1
        error "heap underflow"
    min = A[1]
    A[1] = A[A.heap-size]
    A.heap-size -= 1
    MIN-HEAPIFY(A, 1)
    return min

HEAP-DECREASE-KEY(A, i, key)
    if key > A[i]
        error "new key is bigger than current key"
    A[i] = key
    while i > 1 and A[PARENT(i)] > A[i]
        exchange A[i] with A[PARENT(i)]
        i = PARENT(i)

MIN-HEAP-INSERT(A, key)
    A.heap-size += 1
    A[A.heap-size] = INFINETE
    HEAP-DECREASE-KEY(A, A.heap-size, key)

运行时间都是O(lgn)

练习6.5-4 Why do we bother setting the key of the inserted node to -∞ in line 2 of MAX-HEAP- INSERT when the next thing we do is increase its key to the desired value?

这样可以维护最大堆的性质。

练习6.5-5 Argue the correctness of HEAP-INCREASE-KEY using the following loop invariant: At the start of each iteration of the while loop of lines 4-6, the array A[1…heap- size[A]] satisfies the max-heap property, except that there may be one violation: A[i] may be larger than A[PARENT(i)].

初始：明显成立
保持：只改变一个，就是A[i]，故成立
终止：A[i]就是根元素，故整个堆是最大堆

练习6.5-6 Each exchange operation on line 5 of HEAP-INCREASE-KEY typically requires three asignments. Show how to use the idea of the inner loop of INSERTION-SORT to reduce the three assignments down to just one assignment.

HEAP-INCREASE-KEY(A, i, key)
    if key < A[i]
        error "new key is smaller than current key"
    while i > 1 and A[PARENT(i)] < key
        A[i] = A[PARENT(i)]
        i = PARENT(i)
    A[i] = key

练习6.5-7 Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue. (Queues and stacks are defined in Section 10.1.)

先进先出队列：每次给新插入元素赋更低优先值。
栈：每次给新插入元素赋更高优先值。

练习6.5-8 The operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in O(lg n) time for an n-element max-heap.

This is the wrong implemention.

X HEAP-DELETE(A, i)
X    A[i] = A[A.heap-size]
X    A.heap-size -= 1
X    MAX-HEAPIFY(A, i)

The right one:

HEAP-DELETE(A, i)
    if A[i] < A[A.heap-size]
        HEAP-INCREASE-KEY(A, i, A[A.heap-size])
        A.heap-size -= 1
    else
        A[i] = A[A.heap-size]
        A.heapsize -= 1
        MAX-HEAPIFY(A, i)

练习6.5-9 Give an O(n lg k)-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hint: Use a min-heap for k-way merging.)

def mergeKLists(self, lists):
    """
    :type lists: List[ListNode]
    :rtype: ListNode
    """

    result = []
    BUILD-MIN-HEAP(lists)
    if not lists: return None

    while lists:
        if lists[0] is not None:
            result.append(lists[0].val)
        if lists[0].next:
            MIN-HEAPIFY(lists, 0)
        else:
            HEAP-DELETE(0)
            lists.heap-size -= 1
        lists.delete(0)

始终从最小堆顶部提取元素，故能得到未被放入结果的最小元素。

思考题

6-1

对[1,2,3,4,5,6]生成的就不一样。

T(n) = Θ(lg n!) = Θ(n lg n), 对于递增数列是最坏情况。

6-2 Analysis of d-ary heaps

#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;

#define PARENT(i, d) ((i-1)/d)
#define CHILD(i, c, d) (d*i+c+1)

typedef struct {
    int *elements;
    int d;
    int heap_size;
} heap_t;

void max_heapify(heap_t *heap, int i) 
{
    int largest = i;
    int basechild = CHILD(i, 0, heap->d);

    for (int k = 0; k < heap->d; k++)
    {
        int child = basechild + k;
        if (child < heap->heap_size && heap->elements[child] >
            heap->elements[largest])
            largest = child;
    }

    if (largest != i)
    {
        swap(heap->elements[i], heap->elements[largest]);
        max_heapify(heap, largest);
    }
}

int extract_max(heap_t *heap)
{
    int max = heap->elements[0];
    heap->elements[0] = heap->elements[heap->heap_size - 1];
    heap->heap_size--;
    max_heapify(heap, 0);
    return max;
}

void increase_key(heap_t *heap, int i, int key) 
{
    if (key < heap->elements[i])
    {
        cerr << "new key is smaller than current key" << endl;
        exit(-1);
    }

    while (i > 0 && heap->elements[PARENT(i, heap->d)] < key)
    {
        heap->elements[i] = heap->elements[PARENT(i, heap->d)];
        i = PARENT(i, heap->d);
    }

    heap->elements[i] = key;
}

void insert(heap_t *heap, int key)
{
    heap->heap_size++;
    heap->elements[heap->heap_size-1] = INT_MIN);
    increase_key(heap, heap->heap_size-1, key);
}

a. 
    D-ARR-PARENT(i)
        return floor((i-1)/d)

    D-ARR-CHILD(i, j)
        return d(i-1)+j+2

b. Θ(lg n / lg d)

c.
    MAX-HEAPIFY(A, i, n, d)
        j = i
        for k = 0 to d - 1
            if d*i+k <= n and A[d*i+k]>A[j]
                j = d*i+k
        if j != i
            exchange a[j] with a[i]
            heapify(A, j, n, d)

    时间复杂度 O(dlgn/lgd)

    EXTRACT-MAX
        max = A[1]
        A[1] = A[n]
        n -= 1
        HEAPIFY(A, 1, n, d)
        return max

    时间复杂度 O(dlgn/lgd)

d. 
    INSERT(A, k, n, d)
        n = n + 1
        A[n] = -INFINITE
        INCREASE-KEY(A, i, k, n)

    时间复杂度 O(lgn/lgd)

e.
    INCREASE-KEY(A, i, k)
        A[i] = max(A[i], k)
        if k == A[i]
            while i > 1 and A[floor(i/d)] < A[i]
                exchange A[i] with A[floor(i/d)]
                i = floor(i/d)
        else
            error "WRONG!"

    时间复杂度 O(lgn/lgd)

6-3 Young tableaus

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int EXTRACT-MIN(vector<vector<int>> &young)
{
    int minimum = young[0][0];
    int i(0), j(0);

    while (i < young.size() && j < young[0].size())
    {
        int cur = young[i][j];
        int ori(i), orj(j);
        int right(INT_MAX), down(INT_MAX);

        if (i < young.size()-1) down = young[i+1][j];
        if (j < young[0].size()-1) right = young[i][j+1];

        if (right == INT_MAX && down == INT_MAX)
        {
            young[i][j] = INT_MAX;
            break;
        }
        else if (down <= right)
            i++;
        else
            j++;

        swap(young[i][j], young[ori][orj])
    }

    return minimum;
}

void INSERT(vector<vector<int>> &young, int v)
{
    int i = young.size() - 1;
    int j = young[0].size() - 1;
    young[i][j] = v;

    while(i >= 0 && j >=0)
    {
        int left(INT_MIN), up(INT_MIN);
        
        if(i > 0) up = young[i-1][j];
        if(j > 0) left = young[i][j-1];

        if(v >= up && v >= left)
            break;
        else if(v < up)
        {
            swap(young[i][j], young[i-1][j]);
            i--;
        }
        else
        {
            swap(young[i][j], young[i][j-1]);
            j--;
        }
    }
}

bool EXIST(vector<vector<int>> &young, int v)
{
    int i(young.size()-1), j(0);

    while(i >= 0 && j < young[0].size())
    {
        if(young[i][j] == v)
            reuturn true;

        else if(young[i][j] < v)
            j++;

        else
            i--;
    }

    return false;
}

a.
    2  3  12
    4  8  14
    5  9  16

b.
    It's obvious.

c.
    T(p) = T(p-1) + O(1) = O(p)

d.
    同上。

e. 
    T = n^2 * O(p) = O(n^3)

f. 
    见代码

Sasuke

Jing

CLRS6 堆排序

6.1 堆

6.2 维护堆的性质

6.3 建堆

6.4 堆排序算法

6.5 优先队列

思考题