f676 - FJCU_109_Winter_Day2_Lab5 堆

🔗 前往 ZeroJudge 原題

題目描述

題目要求實作一個二元堆，支援插入數字和輸出最大值並刪除兩種操作。輸入以 EOF 結束，每行包含一個指令，指令可以是 I a (插入數字 a) 或 D (輸出最大值並刪除)。對於每個 D 指令，需要輸出當前堆中的最大值。

解題思路

本題的核心是使用優先佇列 (priority queue) 來模擬二元堆。優先佇列預設會將最大的元素放在頂部，因此可以直接使用 top() 取得最大值，並使用 pop() 刪除最大值。對於插入操作，直接使用 push() 將數字插入優先佇列即可。

複雜度分析

• 時間複雜度: O(n log n)，其中 n 是輸入的指令數量。插入和刪除操作在優先佇列中都是 O(log n)，而題目需要處理 n 個指令。
• 空間複雜度: O(n)，優先佇列最多會儲存 n 個元素。

程式碼

#include <iostream>
#include <queue>
using namespace std;
int main(){
	priority_queue <int> ans;
	char is;
	int n;
	while(cin >> is){
		if(is=='D'){
			cout << ans.top() << "\n";
			ans.pop();
		}
		else{
			cin >> n;
			ans.push(n);
		}
	}
}