[MIT QUIZ]Heap

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 :

$\mathrm{\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 :

$\mathrm{\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 :

$\Theta (n)$

Variation Of Heap

d-ary HEAP

tags: b-tree

Indexing Of Parent/Children

Operation Complexity for max-heap

Insert :

$O({\log }_{d}n)$

Increase-key也是這樣，因為要游上去

1. does 1 comparison at each level of the heap
2. d上升=>高度下降=>變快

Max-Heapify :

$O($

$d$

${\log }_{d}n)$

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

Use Heap to implement queue/stack

tags: queue, stack

Queue

Stack

Treap - BST + Heap

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

Medain or

$k^{th}$ by Heap

Running median using 2 Heap

重點是在兩個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 =

$\mathrm{\Theta }(1)$

Complexity of insertion =

$O(lgn)$

[重要] 找前

$k$ 個大的所有數字

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

概念上是利用一個輔助的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)$

看到

$\log k$要有求smallest/largest問題 => size 為

$k$ 的heap/tree

Similar to problem "Merge k sorted array each with

$\frac{n}{k}$ elements" and "Neighbor find in lower degree graph"
This problem is very tricky

盲點 - 懷疑insert到

$H^{\prime }$的children可能不會包含next largest

如何釐清盲點：用 高度計 的觀點來看，把

$H^{\prime }$中的所有data放進高度計，然後再把要insert進

$H^{\prime }$的data也加進去考慮

heap of heap (click me)的概念雷同

Part 1 : 以每個sub max-heap root建立一個Max-heap (

$H$)-

$O(m)$

$H$不會被變動

Part 2 : 在exract-max之後，把extract-max的data的下面child插入進

$H^{\prime }$

• 可能插入的child 數目
  - 2個：sub max-heap下面的child
  - 4個：每個sub max-heap的root

在對

$H^{\prime }$做extract-max，就是要求的 next largest

Complexity analysis

因為

$H^{\prime }$的size最多會有

$4l$ 個，所以每次的 insertion 和 extract-max 的複雜度都是

$O(\log l)$，然後因為執行

$l$次，所以這部分的複雜度是

$O(l\log l)$

Merge Sort + Heap

[Builind Block] Merge k sorted array each with

$\frac{n}{k}$ elements

Merge Sort跟Heap之間的關係

Naive way -

$\mathrm{\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

如果在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\ast {\log }_{c}n)$

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)

[這個不太會]

Why cannot support extract-min in

$O(1)$

Similar idea