堆排序 存档

userId_undefined

‮队团加不）ด้้童帅_者仇复

尊贵铂金

2024-07-15 14:16:34

发布于：广东

27阅读
0回复
0点赞
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct priority_queue{
	vector <int> __data;
	void push(int tmp){
		__data.push_back(tmp);
		int i = __data.size();
		while(i / 2 >= 1 && __data[i - 1] <= __data[i / 2 - 1]){
			swap(__data[i - 1], __data[i / 2 - 1]);
			i = i / 2;
		}
	}
	int top(){
		if(__data.empty()) return -1;
		return __data[0]; 
	}
	void pop(){
		__data[0] = __data.back();
		__data.pop_back();
		int i = 1;
		while(i * 2 <= __data.size()){
			int j = i * 2;
			if(j < __data.size() && __data[j] < __data[j - 1]) j++;
			if(__data[i - 1] <= __data[j - 1]) return;
			swap(__data[i - 1], __data[j - 1]);
			i = j;
		}
	}
	bool empty(){
		return __data.empty();
	}
	int size(){
		return __data.size();
	}
};
int main(){
	priority_queue q;
	int n, x;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> x;
		q.push(x);
	}
    while(!q.empty()){
        cout << q.top() << ' ';
        q.pop();
    }

	return 0;
}
userId_undefined
去预览
0/2000

全部评论 2

  • userId_undefined

    zth(1000岁老爷爷)

    倔强青铜

    小码君想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数 (N≤100)，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。

    输入格式
    输入有两行，第 1 行为 1 个正整数，表示所生成的随机数的个数 N。

    第 2 行有 N 个用空格隔开的正整数，为所产生的随机数。

    输出格式
    第 1 行为 M 个用空格隔开的正整数，为从小到大排好序的重复的随机数。
    样例组
    输入#1

    10
    20 40 32 67 40 20 89 300 400 15
    输出#1

    20 20 40 40

    2024-07-15 来自 广东

    0
  • userId_undefined

    zth(1000岁老爷爷)

    倔强青铜

    哥，在吗

    2024-07-15 来自 广东

    0

热门讨论