C23panweiming LV 8 @ 2025-3-18 13:16:01

面向对象版的堆

#include<bits/stdc++.h>
using namespace std;
class Heap
{
	private:
		vector<int>heap={-1};
	public:
		int top()
		{
			return heap[1];
		}
		int size()
		{
			return heap.size()-1;
		}
		void up(int x)
		{
			int fa=x/2;
			if(fa>0 && heap[fa]>heap[x])
				swap(heap[fa],heap[x]),up(fa);
		}
		void down(int x)
		{
			int t=x*2;
			if(t+1<=size() && heap[t]>heap[t+1])t++;
			if(t<=size() && heap[x]>heap[t])
				swap(heap[x],heap[t]),down(t);
		}
		void push(int x)
		{
			heap.push_back(x);
			up(size());
		}
		void pop()
		{
			swap(heap[1],heap[size()]);
			heap.pop_back();
			down(1);
		}
};
Heap q;
int main()
{
	int n;
	cin>>n;
	for(int i=1,o;i<=n;i++)
		(cin>>o),q.push(o);
	for(int i=1;i<=n;i++)
		(cout<<q.top()<<" "),q.pop();
	return 0;
}

C24wanghongming LV 3 @ 2025-4-28 13:40:25

C24第一人！！！K124、WZH不是人

#include<bits/stdc++.h>
using namespace std;
template<typename T,typename Comp=less<T>>
struct heap{
    vector<T>tree{1};
    int n=0;
    Comp comp;
    heap(Comp cmp=Comp{}):comp(cmp){}
    T top(){return tree[1];}
	int heap_size(){
		return n;
	}void push(T x){
        n++;
        tree.push_back(x);
        int pthis=n,parent=n/2;
        while(parent>=1&&comp(tree[pthis],tree[parent])){
            swap(tree[pthis], tree[parent]);
            pthis=parent;
            parent/=2;
        }
    }void pop(){
        swap(tree[1],tree[n]);
        tree.pop_back();
        n--;
        int pthis=1;
        while(pthis*2<=n){
            int left=pthis*2,right=pthis*2+1,minchild=left;
            if(right<=n&&comp(tree[right],tree[left]))minchild=right;
			if(comp(tree[minchild],tree[pthis])){
                swap(tree[pthis],tree[minchild]);
                pthis=minchild;
            }else break;
        }
    }
};
int main() {
    heap<int>ppp;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		ppp.push(x);
	}
	for(int i=0;i<n;i++){
		cout<<ppp.top()<<" ";
		ppp.pop();
	}
    return 0;
}

封装好的：(多类型，可传比较函数版)

template<typename T,typename Comp=less<T>>
struct heap{
    vector<T>tree{1};
    int n=0;
    Comp comp;
    heap(Comp cmp=Comp{}):comp(cmp){}
    T top(){return tree[1];}
	long long heap_size(){retern n;}
	void push(T x){
        n++;
        tree.push_back(x);
        int pthis=n,parent=n/2;
        while(parent>=1&&comp(tree[pthis],tree[parent])){
            swap(tree[pthis], tree[parent]);
            pthis=parent;
            parent/=2;
        }
    }void pop(){
        swap(tree[1],tree[n]);
        tree.pop_back();
        n--;
        int pthis=1;
        while(pthis*2<=n){
            int left=pthis*2,right=pthis*2+1,minchild=left;
            if(right<=n&&comp(tree[right],tree[left]))minchild=right;
			if(comp(tree[minchild],tree[pthis])){
                swap(tree[pthis],tree[minchild]);
                pthis=minchild;
            }else break;
        }
    }
};

C24zhuchengyu @ 2025-4-28 13:49:09

楼主别沟吉奥
C24zhuchengyu @ 2025-4-28 13:50:21

666

C23liupeilin LV 7 @ 2025-4-14 19:27:47

堆（class实现）

手打累死了

class mpriority_queue{
	private:
	int a[1000005],tot=0;
	void up(int x){
		if(a[x/2]<a[x]&&x!=1){
			swap(a[x],a[x/2]);
			up(x/2);
		}
	}
	void down(int x){
		if(x*2>tot)return;
		int t=x*2;
		if(x*2+1<=tot)t=a[x*2]>a[x*2+1]?x*2:x*2+1;
		if(a[x]<a[t]){swap(a[x],a[t]);down(t);}
	}
	public:
	void push(int x){
		a[++tot]=x;
		up(tot);
	}
	int top(){return a[1];}
	void pop(){
		swap(a[1],a[tot--]);
		down(1);
	}
}

~~给自己copy的~~

给大家学习+分享+讨论批评的

zengfj LV 7 MOD @ 2025-3-27 14:57:52

堆操作其实很精简就可以写出来。

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, a[N];

void down(int p) {
	int s = p << 1;
	while (s <= n) {
		if (s < n && a[s] < a[s + 1]) s++;
		if (a[s] > a[p]) {
			swap(a[s], a[p]);
			p = s, s = p * 2;
		} else break;
	}
}

void build() {
	// 从最后一个节点的父节点开始，检查并调整使元素符合堆要求。
	// 下标从1开始，parent(i)=(i-1)/2+1
	int len = (n - 1) / 2 + 1;
	for (int i = len; i >= 1; i--) down(i);
}

void hsort() {
	while (n) {
		swap(a[1], a[n]); // 将当前堆顶的元素与当前最后一个元素交换
		n--;
		down(1);
	}
}

int main() {
	int n1;
	cin >> n1;
	// 因为hsort要和down配合，n值会变，所以这里要保存一个n的副本
	n = n1;
	for (int i = 1; i <= n; i++) cin >> a[i];

	build();
	hsort();

	for (int i = 1; i <= n1; i++) cout << a[i] << ' ';

	return 0;
}

C23huangyuran LV 6 @ 2025-3-19 13:04:34

本题为堆排

题意

升序排序。

思路

首先AC。

然后你就得到了一个小根堆。

然后把所有元素Insert进去，再Pop出来，就是升序序列。

为了一个堆走遍堆训练计划，我是采用了面向对象的思想+少量面向过程语法。

class pile{
	private:
		int n=0;
		int a[MaxN];
		void Up(int x){
			if(x==1||a[x]>=a[x>>1]){
				return;
			}
			swap(a[x],a[x>>1]);
			Up(x>>1);
		}
		void Down(int x){
			if(n<x<<1){
				return;
			}
			if(n==x<<1){
				if(a[x]>a[x<<1]){
					swap(a[x],a[x<<1]);
					Down(x<<1);
				}
				return;
			}
			if(a[x]<=a[x<<1]&&a[x]<=a[x<<1|1]){
				return;
			}
			if(a[x]>a[x<<1]&&a[x]<=a[x<<1|1]){
				swap(a[x],a[x<<1]);
				Down(x<<1);
				return;
			}
			if(a[x]>a[x<<1|1]&&a[x]<=a[x<<1]){
				swap(a[x],a[x<<1|1]);
				Down(x<<1|1);
				return;
			}
			if(a[x]>a[x<<1]&&a[x]>a[x<<1|1]){
				if(a[x<<1]<a[x<<1|1]){
					swap(a[x],a[x<<1]);
					Down(x<<1);
					return;
				}
				else{
					swap(a[x],a[x<<1|1]);
					Down(x<<1|1);
					return;
				}
			}
		}
	public:
		int Top(){
			return n?a[1]:-1;
		}
		void Insert(int x){
			a[++n]=x;
			Up(n);
		}
		void Pop(){
			swap(a[1],a[n--]);
			Down(1);
		}
		void debug(){
			cout<<"len: "<<n<<"\npile: ";
			for(int i=1;i<=n;i++){
				cout<<a[i]<<" ";
			}
			cout<<"\n";
		}
};

以上是我的堆。

代码

#include<iostream>
#define MaxN int(2e6)
using namespace std;
class pile{
	private:
		int n=0;
		int a[MaxN];
		void Up(int x){
			if(x==1||a[x]>=a[x>>1]){
				return;
			}
			swap(a[x],a[x>>1]);
			Up(x>>1);
		}
		void Down(int x){
			if(n<x<<1){
				return;
			}
			if(n==x<<1){
				if(a[x]>a[x<<1]){
					swap(a[x],a[x<<1]);
					Down(x<<1);
				}
				return;
			}
			if(a[x]<=a[x<<1]&&a[x]<=a[x<<1|1]){
				return;
			}
			if(a[x]>a[x<<1]&&a[x]<=a[x<<1|1]){
				swap(a[x],a[x<<1]);
				Down(x<<1);
				return;
			}
			if(a[x]>a[x<<1|1]&&a[x]<=a[x<<1]){
				swap(a[x],a[x<<1|1]);
				Down(x<<1|1);
				return;
			}
			if(a[x]>a[x<<1]&&a[x]>a[x<<1|1]){
				if(a[x<<1]<a[x<<1|1]){
					swap(a[x],a[x<<1]);
					Down(x<<1);
					return;
				}
				else{
					swap(a[x],a[x<<1|1]);
					Down(x<<1|1);
					return;
				}
			}
		}
	public:
		int Top(){
			return n?a[1]:-1;
		}
		void Insert(int x){
			a[++n]=x;
			Up(n);
		}
		void Pop(){
			swap(a[1],a[n--]);
			Down(1);
		}
		void debug(){
			cout<<"len: "<<n<<"\npile: ";
			for(int i=1;i<=n;i++){
				cout<<a[i]<<" ";
			}
			cout<<"\n";
		}
}; 
pile a;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){//输入
		int gip;
		cin>>gip;
		a.Insert(gip); 
	} 
	for(int i=1;i<=n;i++){//一个个pop
		cout<<a.Top()<<" ";
		a.Pop();
	}
	return 0;
}

另附->思路

当然作为一个偷懒党，PQ（优先队列）yyds！

但是PQ是大根堆，所以插入就插负数，输出再取负就好了。

代码

十八行精简小代码。

#include<iostream>
#include<queue>
using namespace std;
int main(){
	int n;
	cin>>n;
	priority_queue<int>a;
	for(int i=1;i<=n;i++){
		int gip;
		cin>>gip;
		a.push(-gip);
	}
	for(int i=1;i<=n;i++){
		cout<<-a.top()<<" ";
		a.pop();
	}
	return 0;
}

C23huangminzhe @ 2025-3-19 13:06:08

代码

C23panweiming @ 2025-3-19 13:07:50

#include<bits/stdc++.h>
using namespace std;
class Heap
{
	private:
		vector<int>heap={-1};
	public:
		int top()
		{
			return heap[1];
		}
		int size()
		{
			return heap.size()-1;
		}
		void up(int x)
		{
			int fa=x/2;
			if(fa>0 && heap[fa]>heap[x])
				swap(heap[fa],heap[x]),up(fa);
		}
		void down(int x)
		{
			int t=x*2;
			if(t+1<=size() && heap[t]>heap[t+1])t++;
			if(t<=size() && heap[x]>heap[t])
				swap(heap[x],heap[t]),down(t);
		}
		void push(int x)
		{
			heap.push_back(x);
			up(size());
		}
		void pop()
		{
			swap(heap[1],heap[size()]);
			heap.pop_back();
			down(1);
		}
};
Heap q;
int main()
{
	int n;
	cin>>n;
	for(int i=1,o;i<=n;i++)
		(cin>>o),q.push(o);
	for(int i=1;i<=n;i++)
		(cout<<q.top()<<" "),q.pop();
	return 0;
}

C23huangminzhe @ 2025-3-19 13:09:30

@ 不是快点把你名字换掉啊sab
C23huangminzhe @ 2025-3-19 13:11:53

你的堆为什么叫 pile？
C23huangyuran @ 2025-3-19 13:13:08

@ 我喜欢。
C23huangminzhe @ 2025-3-19 13:13:14

???不要再换成我的名字了！！！！
C23huangyuran @ 2025-3-19 13:13:42

@ 凭什么？
C23huangyuran @ 2025-3-19 13:14:03

@ 被顶替了。。。
C23huangminzhe @ 2025-3-19 13:14:18

@ ~~你侵犯了我的姓名权~~

ID

362

Time

1000ms

Memory

256MiB

Difficulty

Tags

排序

# Submissions

Accepted

Uploaded By

Hydro

5 solutions

C24第一人！！！K124、WZH不是人

封装好的：(多类型，可传比较函数版)

堆（class实现）

本题为堆排

题意

思路

代码

另附->思路

代码

代码

【模板】排序

Information

Status

Development

Support

5 solutions

C24第一人！！！K124、WZH不是人

封装好的：(多类型，可传比较函数版)

堆（class实现）

本题为堆排

题意

思路

代码

另附->思路

代码

代码

【模板】排序

Information

Status

Development

Support

Don't have an account?

SIGN IN