# [MIT QUIZ]Heap
:::success
# Magic Number - ==$\lfloor \frac{n}{2} \rfloor$==
:::

### [How to index]Given a Array, How to check MAX-Heap
### [How to index]Given a MAX-Heap, Where are the possible minimum number?
>跟上面那個類似概念，floor function的概念

### [Bottom-up]Build-Heap : $\Theta(n)$

#### ==Build-Heap ORDER cannot be from the root==
>走到下面時，如果發現下面有比走過的地方還要大的data，那無法被移到上面去，就會產生錯誤。

#### [Top-down]Build-Heap- ==$O(nlgn)$==
連續執行 “Insert” 的動作，每一個步驟執行後均維持MaxHeap
#### Top-Down and Bottom-Up result may be different

### ==Heapsort is unstable==

#### ==如果只有一個node違反heap性質，只對他做max-heapify可能是不夠的==
##### [insertion] 游上去
## Deletion of Heap
### Wrong way to deletion

## Complexity of decrease-key/increase-key : $\Theta (n)$
在max-heap當中
- increase-key: SWAP
- decrease-key: MAX-HEAPIFY

在min-heap當中
- increase-key: MIN-HEAPIFY
- decrease-key: SWAP

### 為什麼會這樣?
因為在max-heap中，
在某一點increase-key可能會違反到上面的data，所以要swap到上面。
在某一點decrease-key的話，不會影響到上面的data，所以對那一個點max-heapify就好。


## Complexity of Find-==Min== in ==MAX==-Heap : $Θ(n)$
:::success
# Variation Of Heap
:::
## d-ary HEAP
###### tags: `b-tree`
### Indexing Of Parent/Children

### Operation Complexity for max-heap
#### Insert : $O(\log_dn)$
>Increase-key也是這樣，因為要游上去

1. does ==1== comparison at each level of the heap
2. d上升=>高度下降=>變快
#### Max-Heapify : $O($==$d$==$\log_dn)$
>extract-max/ __decrease-key__ 也會是這樣

1. does ==d== element comparisons at each level of the heap
2. d上升=>每一層要比較的變多=>變慢
### Height Under Different $d$ <-對不同操作有不同影響
### Complexity under different $d$
#### [Application][SpeedUp for dijkstra](https://hackmd.io/h1SAF0J5S-C5CvKc5IIYAA#SpeedUp-using-d-ary-HEAP)

## Use Heap to implement queue/stack
###### tags: `queue`, `stack`
### Queue
### Stack

## Treap - BST + Heap
:::info
BST invariant比較難maintain，所以先依照BST原則insert，之後有違反heap的property再用rotation的方式修正。
:::

:::success
# Medain or $k^{th}$ by Heap
:::
## Running median using 2 Heap
:::info
重點是在兩個Heap(max-heap/ min-heap)
維持size的關係
:::
>Running median : 一直有數字進來
Max - Heap A < Min - Heap B

### 要刻意維持A和B之間的大小關係
2 case
>1. |A| = |B|+1 => extract-max from A, then insert it to B
>2. |B| = |A|+2 => extrac-min from B, then insert it to A

### Complexity of finding median = ==$\Theta (1)$==
### Complexity of insertion = ==$O(lgn)$==


## ==[重要]== 找前 $k$ 個大的所有數字
:::info
### Max-Heap中前k個大的data並非單純就是Heap中的前面k個！
:::

### All elements in heap :==$O(n+k\log n)$==
### [Improvement] $O(n+k\log$==$k$==$)$
#### Way 1 : Use Oder Statistics
1) Use order statistic algorithm to find the $i$th largest element. Please see the topic selection in worst-case linear time O(n)
2) Use QuickSort Partition algorithm to partition around the kth largest number O(n).
3) Sort the k-1 elements (elements greater than the $i$th largest element) O(iLogi). This step is needed only if sorted output is required.

Time complexity: $O(n)$ if we don’t need the sorted output, otherwise $O(n+ilog$==$i$==$)$
https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/
#### ==[重要]== Way 2 : Use ==[heap-of-heap](https://stackoverflow.com/questions/11209556/print-the-biggest-k-elements-in-a-given-heap-in-oklogk)==

概念上是利用一個輔助的heap，然後原本的heap不會更動到。

### Merge Sort 不管 sequence的sorted程度，複雜度都一樣

> insertion sort 在 sorted的情況下 $O(n)$
### Get $k$ largest element in heap - ==$O(k)$==
> Doesn't need to be sorted
### Range-Bound Input => ==Counting Sort==

## ++[Advanced]++ Largest $l$ number from $m$ max-heap with $n$ elements - ==$O(m+l\log l)$==
:::info
#### 看到$\log k$要有求smallest/largest問題 => size 為 $k$ 的heap/tree
:::
>Similar to problem __"[Merge k sorted array each with $\frac{n}{k}$ elements](https://hackmd.io/o5MDVxCtST24_F-7MCPwug?view#Builind-Block-Merge-k-sorted-array-each-with-fracnk-elements)"__ and __"[Neighbor find in lower degree graph](https://hackmd.io/h1SAF0J5S-C5CvKc5IIYAA?view#Dijkstra-Related-%E2%80%93-Insertion-After-Relaxation)"__
>This problem is very tricky

### 盲點 - 懷疑insert到$H'$的children可能不會包含next largest
如何釐清盲點：用 __高度計__ 的觀點來看，把$H'$中的所有data放進高度計，然後再把要insert進$H'$的data也加進去考慮

### ==[heap of heap](https://hackmd.io/s/H17ervgmV)== (click me)的概念雷同

Part 1 : 以每個sub max-heap root建立一個Max-heap ($H$)- ==$O(m)$==
>$H$不會被變動

Part 2 : 在exract-max之後，把extract-max的data的下面child插入進$H'$
>- 可能插入的child 數目
- 2個：sub max-heap下面的child
- 4個：每個sub max-heap的root

在對$H'$做extract-max，就是要求的 next largest

#### Complexity analysis
因為$H'$的size最多會有 $4l$ 個，所以每次的 __insertion__ 和 __extract-max__ 的複雜度都是$O(\log l)$，然後因為執行$l$次，所以這部分的複雜度是 ==$O(l\log l)$==

:::success
# Merge Sort + Heap
:::
## ==[Builind Block]== Merge k sorted array each with $\frac{n}{k}$ elements
:::info
Merge Sort跟Heap之間的關係
:::

### Naive way - ==$\Theta(kn)$==
>Technique : Same as the Merge Sort

### Using Min-Heap - ==$O(n\log k)$==
> 1. Build Heap of $k$ elements - $O(k)$
> Insert the min of each sorted array into heap
> 2. During each iteration - $O(nlgk)$
> extract-min of heap - $O(lgk)$
> insert the next element in the same list - $O(lgk)$

> Total complexity =$O(nlgk+k)=O(nlgk)$
#### This technique is often used
>extract-min -> insert

similar to the problem __"找前k個大的所有數字"__


## c-Merge Sort
##### tags: `Merge Sort`
>Similar to the problem __"Merge k sorted array each with $\frac{n}{k}$ elements__
:::danger
### 如果在merge那個step沒有用min-heap的話，複雜度就會變成$T(n)=cT(\frac{n}{c})+$==$O(nc)$== = $O(n\log n)$
:::

##### 每次要合併的c個 array 每個都是已經sorted 過的了！


### [Special Case]If c is constant - $T(n)=cT(\frac{n}{c})+O(n)$ = ==$O(n\log n)$==
>Complexity = $T(n)=cT(\frac{n}{c})+O(n\log c)=cT(\frac{n}{c})+O(n)$
>因為c is constant => $O(\log c)=O(1)$


複雜度跟c的大小無關
### [General Case]If c is function of $n$ - $T(n)=cT(\frac{n}{c})+O(n\log c)$= ==$O(n\log c*\log_cn)$==


:::success
# Insertion Sort + Heap
:::
## Nearly Sorted Sequence - fixed distance from final position
Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in __O(nlog k)__ time
>Insertion sort : ==$O(nk)$==
>Heap : Complexity = $O(k) + O((n-k)logk)=$==$O(nlogk)$==

https://www.geeksforgeeks.org/nearly-sorted-algorithm/

# Application
## Coolest person you want to talk to
>用到2個heap
>為了coolness：維持一個max-heap (H)
為了leave time：維持一個min-heap(H’)
如果有人arrive => insert進H’/H
時間到了要extract-min in H’，然後在H對應的node也要被delete
>- 為了支援這個操作，需要維持一個array
(array的index是H’中的index)
(array的value是H中的index)

###
==[這個不太會]==

:::success
# Why cannot support extract-min in ==$O(1)$==
:::
## Similar idea