博客

#include <bits/stdc++.h>
using namespace std;

// 插入法建堆第一位不存放元素即第【0】位不存放元素
template<class T>
void insertBigHeap(T* heap, int n, int a)// heap 为数组， n表示现有元素， a 为插入元素
// 将a插入大根堆，堆中现有n个元素
{
	int i = n + 1;
	while(i > 1 && a > heap[i / 2])// 理解成最后的位置开始上升
	{
		heap[i] = heap[i / 2];
		i = i / 2;// i 指向父节点
		// 根节点编号为0，结点i的父节点编号为（i - 1）/2
		// 若根节点编号为1，则父节点编号为i / 2
	}
	heap[i] = a;
}

// 依次删除最大元素
template<class T>
T delBigHeap(T* heap, int n)// 删除并返回最大元素，因此可作为排序的一种
{
	int now = 1, son; //now 指向要下沉的结点
	T ans = heap[1];
	// 取最后一个元素
	heap[1] = heap[n--];//n--:元素个数
	while(now * 2 <= n)
 	{
		son = now * 2;
		if(son < n && heap[son + 1] > heap[son])
		{
			son++;
		}
		if(heap[now] >= heap[son])
		{
			break;
		}
		else
		{
			T temp = heap[now];
			heap[now] = heap[son];
			heap[son] = temp;
			now = son;
		}
		
 	}
 	return ans;
}

int main()
{
	int n;
	cin >> n;
	int* heap = new int[n];
	int p;
	for (int i = 1; i <= n; i++)
	{
		cin >> p;
		insertBigHeap(heap, i - 1, p);
	}
	for (int i = 1; i <= n; i++)
	{
		cout << heap[i] << " ";
	}
	cout << endl;
	
	
	for (int i = 1; i <= n; i++)
	{
		cout << delBigHeap(heap, n - i + 1) << endl;
	}
}

/*
测试
8
5 6 20 15 17 18 35 19
*/