f650: 今天逗小貓(Heap+-)
Tags : Heap
Accepted rate : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-02-08 21:52

Content

https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E5%A0%86

======================================

. . .

下屬對最大堆積的自上而下調整堆積的虛擬碼中,陣列A的下標索引值是從1開始:

Max-Heapify(Ai):
 left ← 2i
 right ← 2i + 1
 largest ← i
 if left ≤ heap_length[Aand A[left] > A[largestthen:
 largest ← left
 if right ≤ heap_length[Aand A[right] > A[largestthen:
 largest ← right
 if largest ≠ i then:
 swap A[i] ↔ A[largest]
 Max-Heapify(Alargest)

構造二元堆積

一個直觀辦法是從單節點的二元堆積開始,每次插入一個節點。其時間複雜度為O(n\log n)

最佳演算法是從一個節點元素任意放置的二元樹開始,由下而上對每一個子樹執行刪除根節點時的Max-Heapify演算法(這是對最大堆積而言)使得當前子樹成為一個二元堆積。具體而言,假設高度為h的子樹均已完成二元堆積化,那麼對於高度為h+1的子樹,把其根節點沿著最大子節點的分枝做調整,最多需要h步完成二元堆積化。可以證明,這個演算法的時間複雜度為O(n)

建造最大堆積的虛擬碼:

Build-Max-Heap (A):
 heap_length[A] ← length[A]
 for i ← floor(length[A]/2) downto 1 do
 Max-Heapify(Ai)

====================================

在 f498中建構二元堆積的方式是一次加入一個節點,在本題中,我們將要一次給N個節點,放在陣列A[1]...A[N]中,i從N/2的節點開始往上至1(ROOT),做如上的Heapify(A,i)動作完成本題的二元堆積建構。
例如:「Min 8 5 7 9 3 1 4 6 2」代表要建構MinHeap,N=8,原始A陣列為 5 7 9 3 1 4 6 2,經過調整後為 1 2 4 3 7 9 6 5

 

 https://i.imgur.com/AY6FJd5.jpg

 例如:Max 8 5 7 9 3 1 4 6 2」代表要建構MaxHeap,N=8,原始A陣列為 5 7 9 3 1 4 6 2,經過調整後為 9 7 6 3 1 4 5 2

 

https://i.imgur.com/B04KYwI.jpg

Input

每個測資有多組資料{最多10組},每組資料有M+2列,M在每組的第2列

第一列有 N+2個正整數,第1個數字只有1或2代表 1:Min或2:Max,第2個數字N代表一開始給的陣列大小,接著有N個數字x,{1<N<1000、0<x<10000}
第二列有一個正整數M{1<M<1000},代表接著有M個指令,第3列至M+2列共有M個指令,只有三種格式:
1 x y :代表目前顯示A[x]~A[y]的值,含A[x]及A[y],數值間以一個空格隔開, 其中x<=y
2 x : 代表 Push x至Heap
3 : 代表從 Heap中Pop最值, 若Heap已空,不執行此指令

 

Output

只有指令格式1 x y 需顯示一列A[x]~A[y]的值,含A[x]及A[y],數值間以一個空格隔開,若y>N則僅顯示A[x]~A[N]的值
每組資料間以一個空白列隔開

Sample Input #1
1 8 5 7 9 3 1 4 6 2
5
1 1 8
2 8
1 1 9
3
1 1 8
2 8 5 7 9 3 1 4 6 2
5
1 1 8
3
1 1 7
2 8
1 1 8
Sample Output #1
1 2 4 3 7 9 6 5
1 2 4 3 7 9 6 5 8
2 3 4 5 7 9 6 8

9 7 6 3 1 4 5 2
7 3 6 2 1 4 5
8 7 6 3 1 4 5 2
Sample Input #2
1 5 5 8 3 10 4
8
1 1 5
2 9
3
1 1 5
3
2 6
2 3
1 1 6
2 12 8 7 1 4 6 2 11 78 9 45 23 25
10
1 5 15
3
2 15
1 1 10
2 20
3
1 1 12
2 66
2 55
1 1 13
Sample Output #2
3 4 5 10 8
4 8 5 10 9
3 6 5 10 8 9

23 2 11 4 7 6 8 1
45 23 25 9 8 15 11 4 7 6
25 23 20 9 8 15 11 4 7 6 1 2
66 23 55 9 8 20 25 4 7 6 1 2 15
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (33%): 1.0s , <1K
公開 測資點#1 (33%): 1.0s , <1K
公開 測資點#2 (34%): 1.0s , <1K
Hint :

f498: Heap 的進階(Heapify+Push+Pop)
但打不了老虎a091: 今晚打老虎(Deap,Min-Max Heap)

先上題目,會儘快加強測資XDD

Tags:
Heap
出處:
[管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」