对顶堆

标签： index int MaxHeap ELEMENT MinHeap data

对顶堆是由一个大顶堆和一个小顶堆组成的数据结构，用来处理动态求解一个序列中第k大或者第k小的数据结构。其中大顶堆在小顶堆的下面，为什么这样设计呢?

因为如果小顶堆的堆顶大于大顶堆的堆顶,那么对于小顶堆中的所有元素就大于大顶堆中的所有元素了。

原理很简单：根据数学中不等式的传递原理，假如一个集合A中的最小元素比另一个集合B中的最大元素还要大，那么就可以断定：A中的所有元素都比 B 中元素大。所以，我们把小根堆“放在”大根堆“上面”，如果小根堆的堆顶元素比大根堆的堆顶元素大，那么小根堆的所有元素要比大根堆的所有元素大。(堆的性质)

我们要求第 K小的元素，那么我们把大根堆的元素个数限制成K 个，每个元素在入队之前先与大根堆堆顶元素比较，如果比堆顶元素大，就加入小根堆，如果没有的话，将新元素加入大根堆。这样就维护出一个对顶堆。

那么我们就维护了一个对顶堆，我们要求第K小，也就是在求有序之后的序列中的第K个数。

那么从图中可以看出只要大根堆有k个元素，那么第k小的元素就是大根堆的堆顶元素，所有我们只要维护对顶堆的同时，再确保大根堆有k个元素就可以求出序列中第k小的数了。第k大的数同理。

P1801 黑匣子

洛谷题目链接

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 100001
#define ERROR -1

ll a[2 * N];//元素个数最多2 * 10^5所以就开辟这么大的
int n, m;//n为元素的个数
int t;//用来读入命令

typedef ll ELEMENT;

typedef struct heap {
	ELEMENT* data;//´æ·ÅÔªËØµÄÊý×é 
	int size;//×îÐ¡¶ÑÖÐµÄÔªËØ¸öÊý 
	int maxSize;//¶ÑÖÐ×î¶àÄÜ¹»ÈÝÄÉµÄÔªËØ¸öÊý 
}minHeap, * MinHeap;

typedef struct heap1 {
	ELEMENT* data;//´æ·ÅÔªËØµÄÊý×é 
	int size;//×î´ó¶ÑµÄÔªËØ¸öÊý 
	int maxSize;//×î´ó¶Ñ×î¶àÄÜ¹»ÈÝÄÉµÄÔªËØ¸öÊý 
}maxHeap, * MaxHeap;

MaxHeap createMaxHeap(int n);//´´½¨Ò»¸ö×î¶àÄÜ¹»ÈÝÄÉn¸öÔªËØµÄ×î´ó¶Ñ 
int MaxHeapSize(MaxHeap h);//·µ»Ø×î´ó¶ÑµÄÔªËØ¸öÊý
bool isMaxHeapFull(MaxHeap h);//ÅÐ¶Ï×î´ó¶ÑÊÇ²»ÊÇÂúÁË 
bool addMaxHeap(MaxHeap h, ELEMENT item);//Íù×î´ó¶ÑÀïÃæÌí¼ÓÔªËØitem
ELEMENT deleteMaxHeap(MaxHeap h);//µ¯³ö×î´ó¶ÑµÄ¶Ñ¶¥ÔªËØ 
void MaxHeapInsert(MaxHeap h, int index);//ÔÚ×î´ó¶ÑindexÎ»ÖÃÐÂ½øÀ´Ò»¸öÔªËØ£¬ËùÒÔÒªÏòÉÏµ÷Õû£¬À´ÈÃ¶ÑÈÔÈ»ÊÇÒ»¸ö×î´ó¶Ñ 
void MaxHeapify(MaxHeap h, int index);//ÔÚ×î´ó¶ÑindexÎ»ÖÃµÄÔªËØ±äÐ¡ÁË£¬ËùÒÔÏòÏÂµ÷Õû¶Ñ£¬À´ÈÃ¶ÑÈÔÈ»ÊÇÒ»¸ö×î´ó¶Ñ 
bool isMaxHeapEmpty(MaxHeap h);//ÅÐ¶Ï×î´ó¶Ñ¿ÕÁËÃ»ÓÐ 
void swap1(MaxHeap h, int i, int j);//½»»»×î´ó¶ÑÖÐiºÍjÎ»ÖÃµÄÔªËØ 
int MaxHeapCompare(ELEMENT a, ELEMENT b);//»ùÓÚÄ³ÖÐ¹æÔòÀ´±È½Ï,ÀàËÆÓë±È½ÏÆ÷
void freeMaxHeap(MaxHeap h);//ÊÍ·Å×î´ó¶ÑµÄ¿Õ¼ä 
ELEMENT peekMaxHeap(MaxHeap h);//·µ»Ø×î´ó¶ÑµÄ¶Ñ¶¥ÔªËØµ«²»µ¯³ö

MinHeap createMinHeap(int n);//´´½¨Ò»¸ö×î¶àÄÜ¹»ÈÝÄÉn¸öÔªËØµÄ×îÐ¡¶Ñ 
int MinHeapSize(MinHeap h);//·µ»Ø×îÐ¡¶ÑµÄÔªËØ¸öÊý 
bool isMinHeapFull(MinHeap h);//ÅÐ¶Ï×îÐ¡¶ÑÊÇ²»ÊÇÂúÁË 
bool addMinHeap(MinHeap h, ELEMENT item);//Íù×îÐ¡¶ÑÀïÃæÌí¼ÓÔªËØitem
ELEMENT deleteMinHeap(MinHeap h);//µ¯³ö×îÐ¡¶ÑµÄ¶Ñ¶¥ÔªËØ 
void MinHeapInsert(MinHeap h, int index);//ÔÚ×îÐ¡¶ÑindexÎ»ÖÃÐÂ½øÀ´Ò»¸öÔªËØ£¬ËùÒÔÒªÏòÉÏµ÷Õû£¬À´ÈÃ¶ÑÈÔÈ»ÊÇÒ»¸ö×îÐ¡¶Ñ 
void MinHeapify(MinHeap h, int index);//ÔÚ×îÐ¡¶ÑindexÎ»ÖÃµÄÔªËØ±äÐ¡ÁË£¬ËùÒÔÏòÏÂµ÷Õû¶Ñ£¬À´ÈÃ¶ÑÈÔÈ»ÊÇÒ»¸ö×îÐ¡¶Ñ 
bool isMinHeapEmpty(MinHeap h);//ÅÐ¶Ï×îÐ¡¶Ñ¿ÕÁËÃ»ÓÐ 
void swap(MinHeap h, int i, int j);//½»»»×îÐ¡¶ÑÖÐiºÍjÎ»ÖÃµÄÔªËØ 
int MinHeapCompare(ELEMENT a, ELEMENT b);//»ùÓÚÄ³ÖÐ¹æÔòÀ´±È½Ï,ÀàËÆÓë±È½ÏÆ÷ 
void freeMinHeap(MinHeap h);//ÊÍ·Å×îÐ¡¶ÑµÄ¿Õ¼ä 
ELEMENT peekMinHeap(MinHeap h);//µÃµ½×îÐ¡¶ÑÖÐµÄ¶Ñ¶¥ÔªËØ 

int main(int argc, char* argv[])
{
	sc("%d%d", &n, &m);//读入元素的个数和命令

	MinHeap x = createMinHeap(n);//开辟一个最多能容纳n个元素的最小堆
	MaxHeap d = createMaxHeap(n);//开辟一个最多能容纳n个元素的最大堆

	int min = 1;//等于k,就是每次求第几小，刚开始是求第一小，所以初始化为1

	//读入元素到数组里面
	for (int i = 0; i < n; i++) {
		sc("%lld", a + i);
	}

	int k = 0;//用来读入数组里面的元素

	for (int i = 0; i < m; i++) {
		sc("%d", &t);//读入命令

		while (MinHeapSize(x) + MaxHeapSize(d) < t) {//如果没有读到t个元素就一直读
			//维护对顶堆
			if (MaxHeapSize(d) == 0) {//如果最大堆中没有元素，就把数组中的数放入最大堆中，先考虑放在最大堆中
				addMaxHeap(d, a[k++]);//把a[k]放入最大堆
			}
			else {//最大堆中有元素
				if (a[k] >= peekMaxHeap(d)) {//如果取得元素要比最大堆中的堆顶大，那么放入小根堆因为要保证是对顶堆
					addMinHeap(x, a[k++]);//把a[k]放入小根堆
				}
				else {//如果取得元素要比最大堆中的堆顶小，那么放入大根堆因为要保证是对顶堆
					addMaxHeap(d, a[k++]);//把a[k]放入大根堆
				}
			}
		}

		while (MaxHeapSize(d) != min) {//如果最大堆中的元素个数不是k个，也就是不是min个，那么调整对顶堆
			if (MaxHeapSize(d) > min) {//如果最大堆中的元素个数大于min即k，那么就要减少最大堆中的元素，也就是把大根堆中的堆顶元素放入小根堆中
				addMinHeap(x, deleteMaxHeap(d));
			}
			else {//如果最大堆中的元素个数小于min即k，那么就要增加最大堆中的元素，也就是把小根堆中的堆顶元素放入大根堆中
				addMaxHeap(d, deleteMinHeap(x));
			}
		}
		pr("%lld\n", peekMaxHeap(d));//取出大根堆中的堆顶元素，它就是我们要的答案
		min++;//要下一个最小元素
	}

	freeMaxHeap(d);//释放大根堆的空间
	freeMinHeap(x);//释放小根堆的空间

	return 0;
}

MinHeap createMinHeap(int n)
{
	MinHeap h = (MinHeap)malloc(sizeof(minHeap));//¿ª±ÙÒ»¸ö×îÐ¡¶Ñ 

	h->data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//¿ª±ÙÒ»¸ön¸ö¿Õ¼äµÄELEMENTÊý×é 
	h->size = 0;//³õÊ¼»¯×îÐ¡¶ÑÔªËØÊÇ0 
	h->maxSize = n;//×îÐ¡¶ÑÄÜ´æ·Å×î´óÔªËØµÄ¸öÊýÊÇn 

	return h;//·µ»Ø×îÐ¡¶Ñ 
}
int MinHeapSize(MinHeap h)
{
	return h->size;//·µ»Ø×îÐ¡¶ÑÖÐµÄÔªËØ¸öÊý 
}
bool isMinHeapFull(MinHeap h)
{
	return h->size == h->maxSize;//Èç¹û×îÐ¡¶ÑÖÐµÄÔªËØ¸öÊýµÈÓÚÄÜ¹»ÈÝÄÉµÄ×î´óÔªËØ¸öÊý£¬ÄÇÃ´ÂúÁË 
}
bool addMinHeap(MinHeap h, ELEMENT item)
{
	if (isMinHeapFull(h)) {//Èç¹û×îÐ¡¶ÑÒÑ¾ÂúÁË£¬ÄÇÃ´¾Í²»ÄÜÌí¼ÓÔªËØÁË£¬·µ»Øfalse 
		return false;
	}

	h->data[h->size] = item;//°Ñitem·ÅÔÚ×îÏÂ¶ÑÖÐÔªËØ¸öÊýµÄÏÂ±êÖÐ,ÒòÎªÔªËØ¸öÊýµÄÏÂ±ê¾ÍÊÇÒª·ÅµÄÎ»ÖÃ 
	MinHeapInsert(h, h->size);//ÒòÎª¸Õ¸ÕÐÂ½øÀ´Ò»¸öÔªËØ£¬ËùÒÔÏëÈÃ¶Ñ¼ÌÐø±£³Ö×îÐ¡¶Ñ£¬ÄÇÃ´¾ÍÐèÒªÏòÉÏµ÷Õû¶Ñ 
	h->size++;//ÈÃ×îÐ¡¶ÑÖÐµÄÔªËØ¸öÊý¼ÓÒ» 

	return true;//Ìí¼Ó³É¹¦·µ»Øtrue 
}
ELEMENT deleteMinHeap(MinHeap h)
{
	if (isMinHeapEmpty(h)) {//Èç¹û×îÐ¡¶ÑÖÐÃ»ÓÐÔªËØ£¬ÄÇÃ´²»ÄÜ½øÐÐÉ¾³ý£¬Î¥·¨·µ»ØÒ»¸öÌØ¶¨µÄÖµ£¬¼´ERROR 
		return ERROR;
	}

	ELEMENT ans = h->data[0];//·µ»Ø×îÐ¡¶ÑÖÐµÄ¶Ñ¶¥ÔªËØ 
	swap(h, 0, --h->size);//°Ñ×îÐ¡¶ÑÖÐµÄ×îºóÒ»¸öÔªËØÓë¶Ñ¶¥ÔªËØ½øÐÐ½»»»£¬²¢ÇÒÈÃ¶ÑÖÐÔªËØ¼õÒ»£¬ÄÇÃ´¾Í·ÃÎÊ²»µ½¸Õ¸Õ±»É¾³ýµÄÔªËØÁË¡£ 
	MinHeapify(h, 0);//ÏÂ±ê0Î»ÖÃµÄÔªËØ±ä´óÁË£¬ÄÇÃ´ÎªÁË¼ÌÐø±£³ÖÒ»¸ö×îÐ¡¶Ñ£¬¾ÍÒªÏòÏÂµ÷Õû 

	return ans;//·µ»Ø×îÐ¡¶ÑÖÐµÄ¶Ñ¶¥ÔªËØ 
}
void MinHeapInsert(MinHeap h, int index)//indexÎ»ÖÃµÄÊýÏòÉÏµ÷ÕûÐ¡¸ù¶Ñ 
{
	while (MinHeapCompare(h->data[index], h->data[(index - 1) / 2]))//Èç¹ûÏÂ±êindexµÄÖµÐ¡ÓÚËüµÄ¸¸½Úµã 
	{
		swap(h, index, (index - 1) / 2);//ÏÂ±êindexµÄÖµºÍËüµÄ¸¸½ÚµãµÄÖµ½»»» 
		index = (index - 1) / 2;//¸üÐÂindexµÄÎ»ÖÃ 
	}
}
bool isMinHeapEmpty(MinHeap h)
{
	return !h->size;//Èç¹û×îÐ¡¶ÑÖÐµÄÔªËØÊÇ0¸ö£¬ÄÇÃ´¾ÍÊÇ¿Õ£¬ÓÐÔªËØ¾Í²»ÊÇ¿Õ 
}
void swap(MinHeap h, int i, int j)
{
	ELEMENT t = h->data[i];
	h->data[i] = h->data[j];
	h->data[j] = t;
}
void MinHeapify(MinHeap h, int index)
{
	int left = 2 * index + 1;//¼ÆËãÏÂ±êindexµÄ×óº¢×Ó 

	while (left < h->size) {//Èç¹ûÓÐº¢×Ó 
		int lessest = left + 1 < h->size && MinHeapCompare(h->data[left + 1], h->data[left]) ? left + 1 : left;//Èç¹ûÓÐÓÒº¢×Ó²¢ÇÒÓÒº¢×ÓÐ¡ÓÚ×óº¢×Ó£¬ÄÇÃ´º¢×ÓÖÐ×îÐ¡µÄ¾ÍÊÇÓÒº¢×Ó£¬·ñÔò¾ÍÊÇ×óº¢×Ó 

		lessest = MinHeapCompare(h->data[index], h->data[lessest]) ? index : lessest;//Èç¹û¸¸Ç×½Úµã±Èº¢×ÓÖÐ×îÐ¡µÄ»¹ÒªÐ¡£¬ÄÇÃ´×îÐ¡µÄ½Úµã¾ÍÊÇ¸¸½Úµã£¬²»È»×îÐ¡µÄ½Úµã¾ÍÊÇº¢×ÓÖÐ×îÐ¡µÄ½Úµã 

		if (lessest == index) {//Èç¹û×îÐ¡µÄ½ÚµãÊÇ¸¸½Úµã£¬ÄÇÃ´²»ÓÃ¼ÌÐøÁË£¬ÒÑ¾ÊÇ×îÐ¡¶ÑÁË 
			break;
		}

		swap(h, index, lessest);//Óë×îÐ¡µÄº¢×Ó½øÐÐ½»»» 
		index = lessest;//¸üÐÂindexÏÂ±ê£¬ÒòÎª¸Õ¸Õ½»»»ÁË 
		left = 2 * index + 1;//ÖØÐÂ¼ÆËãÏÂ±êindexµÄ×óº¢×Ó 
	}
}
int MinHeapCompare(ELEMENT a, ELEMENT b)
{
	return a < b;//Ö±½Ó½øÐÐÖµµÄ±È½Ï 
}
void freeMinHeap(MinHeap h)
{
	free(h->data);//ÏÈÊÍ·Å×îÐ¡¶Ñ´æ·ÅÔªËØµÄ¿Õ¼ä 
	free(h);//ÔÙÊÍ·Å×îÐ¡¶ÑµÄ¿Õ¼ä 
}
ELEMENT peekMinHeap(MinHeap h)
{
	if (isMinHeapEmpty(h)) {//×îÐ¡¶ÑÀïÃæÃ»ÓÐÔªËØÄÇÃ´£¬²Ù×÷Î¥·¨£¬·µ»ØÌØ¶¨Öµ 
		return ERROR;
	}

	ELEMENT ans = deleteMinHeap(h);//µ¯³ö×îÐ¡¶ÑµÄ¶Ñ¶¥ 

	addMinHeap(h, ans);//ÔÙ·ÅÈë×îÐ¡¶Ñ£¬ÒÔ´ËÀ´ÊµÏÖ´úÂë¸´ÓÃ 

	return ans;//·µ»Ø×îÐ¡¶ÑµÄ¶Ñ¶¥ÔªËØ 
}

MaxHeap createMaxHeap(int n)
{
	MaxHeap h = (MaxHeap)malloc(sizeof(maxHeap));//¿ª±ÙÒ»¸ö×î´ó¶Ñ 

	h->data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//¿ª±ÙÒ»¸ö¿ÉÒÔ´æ·Ån¸öÔªËØµÄÊý×é 
	h->size = 0;//³õÊ¼»¯×î´ó¶ÑÔªËØÊÇ0 
	h->maxSize = n;//×î´ó¶ÑÄÜ´æ·Å×î´óÔªËØµÄ¸öÊýÊÇn

	return h;//·µ»Ø×î´ó¶Ñ 
}
int MaxHeapSize(MaxHeap h)
{
	return h->size;//·µ»Ø×î´ó¶ÑÖÐµÄÔªËØ¸öÊý
}
bool isMaxHeapFull(MaxHeap h)
{
	return h->size == h->maxSize;//Èç¹û×î´ó¶ÑÖÐµÄÔªËØ¸öÊýµÈÓÚÄÜ¹»ÈÝÄÉµÄ×î´óÔªËØ¸öÊý£¬ÄÇÃ´ÂúÁË
}
bool addMaxHeap(MaxHeap h, ELEMENT item)
{
	if (isMaxHeapFull(h)) {//Èç¹û×î´ó¶ÑÒÑ¾ÂúÁË£¬ÄÇÃ´¾Í²»ÄÜÌí¼ÓÔªËØÁË£¬·µ»Øfalse 
		return false;
	}

	h->data[h->size] = item;//°Ñitem·ÅÔÚ×îÏÂ¶ÑÖÐÔªËØ¸öÊýµÄÏÂ±êÖÐ,ÒòÎªÔªËØ¸öÊýµÄÏÂ±ê¾ÍÊÇÒª·ÅµÄÎ»ÖÃ 
	MaxHeapInsert(h, h->size);//ÒòÎª¸Õ¸ÕÐÂ½øÀ´Ò»¸öÔªËØ£¬ËùÒÔÏëÈÃ¶Ñ¼ÌÐø±£³Ö×î´ó¶Ñ£¬ÄÇÃ´¾ÍÐèÒªÏòÉÏµ÷Õû¶Ñ 
	h->size++;//ÈÃ×î´ó¶ÑÖÐµÄÔªËØ¸öÊý¼ÓÒ» 

	return true;//Ìí¼Ó³É¹¦·µ»Øtrue 
}
ELEMENT deleteMaxHeap(MaxHeap h)
{
	if (isMaxHeapEmpty(h)) {//Èç¹û×î´ó¶ÑÖÐÃ»ÓÐÔªËØ£¬ÄÇÃ´²»ÄÜ½øÐÐÉ¾³ý£¬Î¥·¨·µ»ØÒ»¸öÌØ¶¨µÄÖµ£¬¼´ERROR
		return ERROR;
	}

	ELEMENT ans = h->data[0];//·µ»Ø×î´ó¶ÑÖÐµÄ¶Ñ¶¥ÔªËØ 
	swap1(h, 0, --h->size);//°Ñ×î´ó¶ÑÖÐµÄ×îºóÒ»¸öÔªËØÓë¶Ñ¶¥ÔªËØ½øÐÐ½»»»£¬²¢ÇÒÈÃ¶ÑÖÐÔªËØ¼õÒ»£¬ÄÇÃ´¾Í·ÃÎÊ²»µ½¸Õ¸Õ±»É¾³ýµÄÔªËØÁË¡£
	MaxHeapify(h, 0);//ÏÂ±ê0Î»ÖÃµÄÔªËØ±äÐ¡ÁË£¬ÄÇÃ´ÎªÁË¼ÌÐø±£³ÖÒ»¸ö×î´ó¶Ñ£¬¾ÍÒªÏòÏÂµ÷Õû 

	return ans;//·µ»Ø×î´ó¶ÑÖÐµÄ¶Ñ¶¥ÔªËØ 
}
void MaxHeapInsert(MaxHeap h, int index)//indexÎ»ÖÃµÄÊýÏòÉÏµ÷Õû´ó¸ù¶Ñ 
{
	while (MaxHeapCompare(h->data[index], h->data[(index - 1) / 2]))//Èç¹ûÏÂ±êindexµÄÖµ´óÓÚËüµÄ¸¸½Úµã 
	{
		swap1(h, index, (index - 1) / 2);//ÏÂ±êindexµÄÖµºÍËüµÄ¸¸½ÚµãµÄÖµ½»»» 
		index = (index - 1) / 2;//¸üÐÂindexµÄÎ»ÖÃ 
	}
}
bool isMaxHeapEmpty(MaxHeap h)
{
	return !h->size;//Èç¹û×î´ó¶ÑÖÐµÄÔªËØÊÇ0¸ö£¬ÄÇÃ´¾ÍÊÇ¿Õ£¬ÓÐÔªËØ¾Í²»ÊÇ¿Õ 
}
void swap1(MaxHeap h, int i, int j)
{
	ELEMENT t = h->data[i];
	h->data[i] = h->data[j];
	h->data[j] = t;
}
void MaxHeapify(MaxHeap h, int index)
{
	int left = 2 * index + 1;//¼ÆËãÏÂ±êindexµÄ×óº¢×Ó 

	while (left < h->size) {//Èç¹ûÓÐº¢×Ó 
		int largest = left + 1 < h->size && MaxHeapCompare(h->data[left + 1], h->data[left]) ? left + 1 : left;//Èç¹ûÓÐÓÒº¢×Ó²¢ÇÒÓÒº¢×Ó´óÓÚ×óº¢×Ó£¬ÄÇÃ´º¢×ÓÖÐ×î´óµÄ¾ÍÊÇÓÒº¢×Ó£¬·ñÔò¾ÍÊÇ×óº¢×Ó

		largest = MaxHeapCompare(h->data[index], h->data[largest]) ? index : largest;//Èç¹û¸¸Ç×½Úµã±Èº¢×ÓÖÐ×î´óµÄ»¹Òª´ó£¬ÄÇÃ´×î´óµÄ½Úµã¾ÍÊÇ¸¸½Úµã£¬²»È»×î´óµÄ½Úµã¾ÍÊÇº¢×ÓÖÐ×î´óµÄ½Úµã 

		if (largest == index) {//Èç¹û×î´óµÄ½ÚµãÊÇ¸¸½Úµã£¬ÄÇÃ´²»ÓÃ¼ÌÐøÁË£¬ÒÑ¾ÊÇ×î´ó¶ÑÁË
			break;
		}

		swap1(h, index, largest);//Óë×î´óµÄº¢×Ó½øÐÐ½»»» 
		index = largest;//¸üÐÂindexÏÂ±ê£¬ÒòÎª¸Õ¸Õ½»»»ÁË
		left = 2 * index + 1;//ÖØÐÂ¼ÆËãÏÂ±êindexµÄ×óº¢×Ó
	}
}
int MaxHeapCompare(ELEMENT a, ELEMENT b)
{
	return a > b;//Ö±½Ó½øÐÐÖµµÄ±È½Ï
}
void freeMaxHeap(MaxHeap h)
{
	free(h->data);//ÏÈÊÍ·Å×î´ó¶Ñ´æ·ÅÔªËØµÄ¿Õ¼ä 
	free(h);//ÔÙÊÍ·Å×î´ó¶ÑµÄ¿Õ¼ä 
}
ELEMENT peekMaxHeap(MaxHeap h)
{
	if (isMaxHeapEmpty(h)) {//×î´ó¶ÑÀïÃæÃ»ÓÐÔªËØÄÇÃ´£¬²Ù×÷Î¥·¨£¬·µ»ØÌØ¶¨Öµ 
		return ERROR;
	}

	ELEMENT ans = deleteMaxHeap(h);//µ¯³ö×î´ó¶ÑµÄ¶Ñ¶¥ 

	addMaxHeap(h, ans);//ÔÙ·ÅÈë×î´ó¶Ñ£¬ÒÔ´ËÀ´ÊµÏÖ´úÂë¸´ÓÃ 

	return ans;//·µ»Ø×î´ó¶ÑµÄ¶Ñ¶¥ÔªËØ 
}

标签：,index,int,MaxHeap,ELEMENT,MinHeap,data
From： https://www.cnblogs.com/lwj1239/p/17997822

P1801 黑匣子

代码实现

相关文章

赞助商

阅读排行