f650. 今天逗小貓(Heap+-) - 高中生程式解題系統

內容

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

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

．．．

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

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

構造二元堆積

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

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

建造最大堆積的虛擬碼：

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

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

在 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

輸入說明

每個測資有多組資料{最多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已空，不執行此指令

輸出說明

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

範例輸入 #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

範例輸出 #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

範例輸入 #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

範例輸出 #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

提示：

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

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

標籤:

Heap

出處:

[管理者： p3a_owhj (阿普二信) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」

． ． ．

構造二元堆積

．．．