最小堆,玄关求调
查看原帖
最小堆,玄关求调
1366636
johnCh楼主2024/8/7 11:58
#include <bits/stdc++.h>
using namespace std;

template <class T>
class Heap
{
	void minHeapify(T a[], T i, T n)
	{
		int ls, rs;
		while (i <= n)
		{
			ls = i << 1;
			rs == i << 1 | 1;
			if (a[i] <= a[ls] && a[i] <= a[rs])
				break;
			else if (a[i] > a[ls] && a[i] > a[rs])
			{
				int ct = (a[ls] < a[rs]) ? ls : rs;
				swap(a[i], a[ct]);
				i = ct;
			}
			else if (a[i] > a[ls])
			{
				swap(a[i], a[ls]);
			}
			else
			{
				swap(a[i], a[rs]);
			}
		}
	}
	void build_heap(T a[], T n)
	{
		for (int i = n / 2; i >= 1; i--)
		{
			minHeapify(a, i, n);
		}
	}

public:
	void sort(T a[], T n)
	{
		build_heap(a, n);
		for (int i = n; i >= 2; i--)
		{
			swap(a[1], a[i]);
			this->minHeapify(a, 1, i - 1);
		}
	}
};
Heap<int> heap;
int a[1000001], tot;
int main()
{
	int q;
	cin >> q;
	for (int i = 1; i <= q; i++)
	{
		int opt;
		cin >> opt;
		if (opt == 1)
		{
			int tmp;
			cin >> tmp;
			a[++tot] += tmp;
		}
		else if(opt = 2)
		{
			heap.sort(a, tot);
			cout << a[tot] << endl;
		}
		
		else if(opt = 3)
		{
			heap.sort(a, tot);
			a[tot] = 0;
			tot--;
		}
	}
	return 0;
}

报错信息:

Program received signal SIGSEGV, Segmentation fault.
in Heap::minHeapify (this=0x4a7040 , a=0x4a7080 , i=1, n=2) at Line 14
14 : if (a[i] <= a[ls] && a[i] <= a[rs])

2024/8/7 11:58
加载中...