Heap

tags: 資料結構 排序法

Heap 定義

A heap T is a complete binary tree in which either T is empty or

1. left child is less than or equal to root
2. right child is greater than or equal to root
3. 適合用 array 來實作，root為 i(index)，left child = 2i+1 and right child = 2i+2
4. Heap is a ordered Binary tree
5. 適合 implements Priority Queue

註：前三點為 Max Heap
註：complete binary tree 只能最下最右的兒子缺少，index需與 full binary tree一樣

Heap介紹

---

以下程式碼解法根據台大研究所計算機概論考古題來解題

---

Heapify

pseudocode

用來檢查Heap是否滿足Max Heap or Min Heap ( root>left && root>right )

1. Init： int i=0; int l=2i+1; int r=2i+2; int large=i;
2. 比較root是否比left小，且left小於n，若是large = l;
3. 比較root是否比right小，且right小於n，若是large = r;
4. 檢查 i != large, then swap A[i] and A[large]
5. recursive heapify(arr,n,large)

void heapify(int arr[], int n, int i) 
{ 
    int largest = i; 
    int l = 2 * i + 1;
    int r = 2 * i + 2; 
  
    if (l < n && arr[l] > arr[largest]){
        largest = l; 
    } 
    if (r < n && arr[r] > arr[largest]){
        largest = r;
    } 
    if (largest != i) { 
        swap(arr[i], arr[largest]);  
        heapify(arr, n, largest); 
    } 
} 

---

Insert element

pseudocode

1. add node on the last of array
2. compare with its father node, if newNode > father then swap
3. while ( node = root || node < father )

圖片來源：https://algorithms.tutorialhorizon.com/binary-min-max-heap/

bool insert(int newValue){
    if(itemCount==100){
        return false 
    }else{
        items[itemCount] == newValue;
        int i=itemCount;
        int j=(i-1)/2; 不用管左子樹右子樹，因為-1/2都會對應到父節點
        int temp;
        while(i>0){
            if(items[i]>items[j]){
                temp = items[j];
                items[j] = items[i];
                items[i] = temp;
                i = j;    繼續搜尋下一個父節點
                j = (i-1)/2;
            }else{
                i = 0;    把i設為0跳出while迴圈
            }
        }
    }
}

---

Delete root

pseudocode

1. swap root and the node on the last of array
2. remove root(now on the last of array)
3. compare the newRoot to others, if newRoot is smaller then swap => Heapify newRoot
4. while do step 3

圖片來源：https://iowiki.com/data_structures_algorithms/heap_data_structure.html

int delete(){
    if(itemCount==0){
        return -1;
    }else{
        int removeNode = items[0];
        int last = items[itemCount-1];
        items[0] = last;
        itemCount = itemCount-1;
        heapify(items,itemCount,0);
        return removeNode;
    }
}

---

相關文章：HeapSort