iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 10

Day-10 heap與heap sort

Heap

Heap(堆積)是一個陣列,可以把它看作類似完全二元樹(也就是按照順序排放的樹)。
p.s : 樹是一種資料結構,大部分的操作時間複雜度平均為https://chart.googleapis.com/chart?cht=tx&chl=O(lgn)樹將在後面介紹~~

樹上每一個節點,對應到陣列中的一個元素。除了樹的最底層以外,該樹是完全填滿的,填充的規則為由左向右進行填充。

表示Heap的陣列通常會具有兩個屬性,https://chart.googleapis.com/chart?cht=tx&chl=A.length表示陣列中元素的個數,https://chart.googleapis.com/chart?cht=tx&chl=A.heap-size表示Heap中元素的個數。

樹的根結點為https://chart.googleapis.com/chart?cht=tx&chl=A%5B1%5D,給定陣列的index i進行走訪,可以根據index來得到樹的父節點,左子節點和右子節點

PARENT(i)
    return i/2
LEFT_CHILD(i)
    return 2i
RIGHT_CHILD(i)
    return 2i + 1


假設i = 2,則LEFT_CHILD = 4,元素為8,RIGHT_CHILD = 5,元素為7,PARENT = 2,元素為14。

二元堆積(Binary heap)可以分成兩種,最大堆積(max heap)和最小堆積(min heap),在這兩種heap中,都需要滿足heap的性質。

  • 最大堆積(max heap) : 父節點的值>=子節點的值, https://chart.googleapis.com/chart?cht=tx&chl=A%5BPARENT(i)%5D%20%3E%3D%20A%5Bi%5D
  • 最小堆積(min heap) : 父節點的值<=子節點的值, https://chart.googleapis.com/chart?cht=tx&chl=A%5BPARENT(i)%5D%20%3C%3D%20A%5Bi%5D

以上面這個例子,即為max heap。但是有可能有一個heap不屬於上面這兩種,假設陣列沒有先經過排序,只會產生出heap,他不屬於max heap,也不屬於min heap。

在heap sort中,通常會使用max heap。min heap通常用來實作priority heap。在特定的應用中,才會明確的說使用的是min heap還是max heap,當兩者皆可時,通常直接以heap來描述。

如果直接把heap當作一棵樹,定義一個heap中的節點高度為某一個節點由上往下找到達葉節點所經過的最大邊數,如2號節點其高度為2。而拓展這個定義,可以得到整個heap的高度為樹根到業節點所經過的最大邊數,因此這個heap的高度為3。

一個包含n個元素的陣列可以看做一個完全二元樹,那麼該heap的高度為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(lgn)。對於heap的操作基本上和樹的高度成正比,也就是時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(lgn),以下為一些針對heap的操作

  • MAX-HEAPIFY : 用於維持max heap的性質,時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(lgn)
  • BUILD-MAX-HEAP : 將無序的陣列轉變成一個max heap。
  • HEAPSORT : 對一個陣列進行原地(in place)排序,

以下操作是針對priority heap

  • MAX-HEAP-INSERT : 插入一個元素到heap
  • HEAP-EXTRACT-MAX : 回傳最大值,並將該最大值從heap中移除
  • HEAP-INCREASE-KEY : 把x對應到的權重(鍵值)增加到k上面
  • HEAP-MAXUNIUM : 回傳最大值

MAX-HEAPIFY

MAX-HEAPIFY是用來維持max heap。他的參數為陣列A和一個下標i。

呼叫MAX-HEAPIFY時,會假定根節點https://chart.googleapis.com/chart?cht=tx&chl=A%5Bi%5D的兩棵子樹結點LEFT(i)和RIGHT(i)都符合max heap,如果不符合,便將https://chart.googleapis.com/chart?cht=tx&chl=A%5Bi%5D的值在max heap中一階一階的下降,直到A[i]的兩棵子樹LEFT(i)和RIGHT(i)都符合max heap。

如果我們呼叫MAX-HEAPIFY(Array, 2),會發現他的值並不大於LEFT(i),這並不符合max heap的規則,因此,交換https://chart.googleapis.com/chart?cht=tx&chl=A%5B2%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=A%5B4%5D的值,讓第2號節點符合max heap的性質。

在上一步的操作雖然讓第2號節點符合max heap的規則,但是它使第4號節點違反max heap的規則,因此,遞迴呼叫MAX-HEAPIFY(A, 4),發現https://chart.googleapis.com/chart?cht=tx&chl=A%5B4%5D比RIGHT(i)還要小,因此交換https://chart.googleapis.com/chart?cht=tx&chl=A%5B4%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=A%5B9%5D

交換之後,遞迴呼叫MAX-HEAPIFY(A, 9),發現條件皆不成立,因此甚麼都不做。

虛擬碼如下

MAX-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l <= A.heap-size and A[l] > A[i]
        largest = l
    else largest = 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)

MAX-HEAPIFY效率

對於一棵以i為根節點,大小為n的子樹,MAX-HEAPIFY所需要的時間代價為,調整https://chart.googleapis.com/chart?cht=tx&chl=A%5Bi%5D,https://chart.googleapis.com/chart?cht=tx&chl=A%5BLEFT(i)%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=A%5BRIGHT(i)%5D之間的關係時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(1),加上在一棵以i的一個子節點產生出的子樹呼叫MAX-HEAPIFY的時間,每個子節點所產生的子樹大小最大為https://chart.googleapis.com/chart?cht=tx&chl=2n%2F3(會發生在樹的底層恰好為半滿的時候),可以用下面的遞迴關係式表示MAX-HEAPIFY的執行時間:

https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3C%3D%20T(2n%2F3)%20%2B%20%5CTheta(1),使用主定理得到https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20O(lgn),含有https://chart.googleapis.com/chart?cht=tx&chl=n個元素的heap高度為https://chart.googleapis.com/chart?cht=tx&chl=lgn,也就是說,對於高度為https://chart.googleapis.com/chart?cht=tx&chl=h的heap來說,MAX-HEAPIFY的效率為https://chart.googleapis.com/chart?cht=tx&chl=O(h)

BUILD-MAX-HEAP

由下而上透過呼叫MAX-HEAPIFY將一個大小為https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%20A.length的陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5B1...n%5D轉變成max heap。子陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bn%2F2%20%2B%201%20...n%5D中的元素皆為樹的葉節點。每一個葉節點可以當作是只有一個元素heap。透過由下而上不斷呼叫MAX-HEAPIFY完成BUILD-MAX-HEAP。

BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = A.length/2 downto 1
    MAX-HEAPIFY(A, i)
  1. 呼叫MAX-HEAPIFY(A, 5)
  2. 呼叫MAX-HEAPIFY(A, 4)
  3. 呼叫MAX-HEAPIFY(A, 3)
  4. 呼叫MAX-HEAPIFY(A, 2)
  5. 呼叫MAX-HEAPIFY(A, 1)

    完成

BUILD-MAX-HEAP效率

每一次呼叫MAX-HEAPIFY根據上面的推導,可以得到需要https://chart.googleapis.com/chart?cht=tx&chl=O(lgn),BUILD-MAX-HEAP需要https://chart.googleapis.com/chart?cht=tx&chl=O(n)次呼叫,因此總時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(nlgn),雖然這是一個正確的上界,但卻不夠逼近函數。

我們可以試著求出更加逼近這個函數的上界。可以觀察到,執行MAX-HEAPIFY的時間與該節點的樹高有關,而且大部分的節點高度都比較小,這也是我們使用https://chart.googleapis.com/chart?cht=tx&chl=O(nlgn)產生出不夠逼近的上界的原因,我們可以使用樹的性質去求出更精確地上界,含有https://chart.googleapis.com/chart?cht=tx&chl=n個元素的heap高度為https://chart.googleapis.com/chart?cht=tx&chl=lgn,高度為https://chart.googleapis.com/chart?cht=tx&chl=h的heap最多有https://chart.googleapis.com/chart?cht=tx&chl=n%2F2%5E%7Bh%2B1%7D個節點

對於高度為https://chart.googleapis.com/chart?cht=tx&chl=h的heap,MAX-HEAPIFY的時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(h),因此,我們可以將BUILD-MAX-HEAP的時間代價以下面這個式子表示
https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7Bh%3D0%7D%5E%7Blgn%7D(%5Cfrac%20n%20%7B2%5E%7Bh%20%2B%201%7D%7DO(h))%20%3D%20O(n%5Csum_%7Bh%20%3D0%7D%5E%7Blgn%7D%20%5Cfrac%20h%20%7B2%5Eh%7D)
https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7Bh%20%3D%200%7D%5E%7B%5Cinfty%7D%20%5Cfrac%20h%20%7B2%5Eh%7D%20%3D%20%5Cfrac%20%7B1%2F2%7D%20%7B(1-1%2F2)%5E2%7D%20%3D%202
於是,整個BUILD-MAX-HEAP的時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(n%5Csum_%7Bh%20%3D%200%7D%5E%7Blgn%7D%20%5Cfrac%20h%20%7B2%5Eh%7D)%20%3D%20O(n%5Csum_%7Bh%20%3D0%7D%5E%7Blgn%7D%20%5Cfrac%20h%20%7B2%5Eh%7D)%20%3D%20O(2n)%20%3D%20O(n)

Heap sort

最一開始,Heap sort會呼叫BUILD-MAX-HEAP將輸入的陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5B1...n%5D變成max heap。

因為陣列中最大元素總是在根節點,也就是https://chart.googleapis.com/chart?cht=tx&chl=A%5B1%5D中,我們把它和https://chart.googleapis.com/chart?cht=tx&chl=A%5Bn%5D進行交換,並將https://chart.googleapis.com/chart?cht=tx&chl=A%5Bn%5D從heap中去除,也就是彈出目前heap的最大節點,經過這樣的操作我們會發現原來根節點的子節點仍然會維持max heap,但是根節點可能會違反max heap的規則。

為了維持max heap,我們呼叫NAX-HEAPIFY(A, 1),在https://chart.googleapis.com/chart?cht=tx&chl=A%5B1...n-1%5D上建造出新的max heap,直到heap的大小從https://chart.googleapis.com/chart?cht=tx&chl=n%20-%201下降到https://chart.googleapis.com/chart?cht=tx&chl=2

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

初始狀態,呼叫BUILD-MAX-HEAP建造出max heap

彈出heap中最大元素,並MAX-HEAPIFY










整個思路就是運用max heap的最大節點會在根節點的特性去完成排序。

heap sort的時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(nlgn),呼叫BUILD-MAX-HEAP的時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(n),而呼叫了https://chart.googleapis.com/chart?cht=tx&chl=n%20-%201次MAX-HEAPIFY,每一次呼叫MAX-HEAPIFY的時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(lgn),因此整個heap sort時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(lgn)

實作 :

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct object
{
    int array[11] = {-1, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
    int heap_size = 10;
    int array_size = 10;
} object;
void max_heapify(object *, int);
void build_max_heap(object *);
void heap_sort(object *);
int parent(int);
int left_child(int);
int right_child(int);
int main(void)
{
    object A;
    heap_sort(&A);
    for (int i = 1; i < 11; i++)
    {
        cout << A.array[i] << ' ';
    }
}
int parent(int i)
{
    if (i == 0)
    {
        return 0;
    }
    return i / 2;
}

int left_child(int i)
{
    return 2 * i;
}

int right_child(int i)
{
    return (2 * i) + 1;
}

void max_heapify(struct object *A, int i)
{
    int l = left_child(i);
    int r = right_child(i);
    int largest = 0;
    if ((l <= A->heap_size) && (A->array[l] > A->array[i]))
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if ((r <= A->heap_size) && (A->array[r] > A->array[largest]))
    {
        largest = r;
    }
    if (largest != i)
    {
        swap(A->array[i], A->array[largest]);
        max_heapify(A, largest);
    }
}

void build_max_heap(object *A)
{
    A->heap_size = A->array_size;
    for (int i = A->array_size / 2; i >= 1; i--)
    {
        max_heapify(A, i);
    }
}

void heap_sort(object *A)
{
    build_max_heap(A);
    for (int i = A->heap_size; i >= 2; i--)
    {
        swap(A->array[1], A->array[i]);
        A->heap_size = A->heap_size - 1;
        max_heapify(A, 1);
    }
}

(直到鐵人賽第10天,才知道自己記錯了書名...)
參考資料:Introduction to algorithms 3rd


上一篇
Day-9 Divide-and-Conquer-4 : Quicksort, 隨機化Quicksort
下一篇
Day-11 priority queue
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言