f498 - Heap
題目描述
題目要求實作一個 min heap 和一個 max heap，並以 level order 的方式輸出兩個 heap 的元素。輸入包含多組測試案例，每組案例先輸入一個整數 n，表示接下來有 n 個整數要插入 heap。然後輸入 n 個整數，這些整數將被分別插入 min heap 和 max heap。對於每組測試案例，程式需要輸出 min heap 和 max heap 的 level order 輸出。
解題思路
程式碼使用兩個陣列 a 和 b 分別儲存 max heap 和 min heap。程式碼使用自底向上（bottom-up）的方式建構 heap。對於每個輸入數字，先將其插入 a (max heap) 和 b (min heap)，然後從該數字的位置開始，向上比較並交換，直到滿足 heap 的性質。對於 max heap，如果當前節點的值大於其父節點的值，則交換它們。對於 min heap，如果當前節點的值小於其父節點的值，則交換它們。建構完 heap 之後，程式碼以 level order 的方式輸出 b (min heap) 和 a (max heap) 的元素。
複雜度分析
- 時間複雜度: O(n log n) 建構 heap 的時間複雜度為 O(n log n)，因為對於每個元素，我們最多需要向上移動 log n 層才能找到其正確位置。輸出 heap 的時間複雜度為 O(n)。因此，總時間複雜度為 O(n log n)。
- 空間複雜度: O(n)
程式碼使用兩個大小為 n 的陣列
a和b儲存 heap，因此空間複雜度為 O(n)。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define swap(x,y) { x = x + y; y = x - y; x = x - y; }
#include <stdio.h>
int a[1025],b[1025],n;
inline int read(){
int a(0),f(1);
char c('0');
while(c>='0'||c=='-'){
if(c=='-'){
f=-1;
c=getchar_unlocked();
}
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a*f;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
while(n=read()){
for(int i=1,tmp=1;i<=n;++i,tmp=i){
a[i]=read();
b[i]=a[i];
while(tmp>>1){
if(a[tmp]>a[tmp>>1])
swap(a[tmp],a[tmp>>1]);
if(b[tmp]<b[tmp/2])
swap(b[tmp],b[tmp>>1]);
tmp>>=1;
}
}
for(int j=1;j<=n;++j){
write(b[j]);
putchar_unlocked(' ');
}
putchar_unlocked('\n');
for(int j=1;j<=n;++j){
write(a[j]);
putchar_unlocked(' ');
}
putchar_unlocked('\n');
}
}