# 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介紹](https://www.youtube.com/watch?v=0wPlzMU-k00&ab_channel=MichaelSambol)

---

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

---

### 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](https://hackmd.io/fL8XbK_eQ-m4LBdtfnoq4Q)