C++最大堆实现priority_queue优先级队列（算法导论）

max_heapify与build_max_heap过程与heapsort一样

#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;

const int INT_MIN = -(1 << 31);
inline void swap(int &a, int &b) { int t = a; a = b; b = t; }
inline int parent(int i) { return (i-1) >> 1; }         //下标都是从0开始，与算导上不一样
inline int left(int i) { return (i << 1) + 1; }
inline int right(int i) { return (i << 1) + 2; }

int heap_size, heap_length;          //heap_length是数组元素个数，heap_size是有多少个元素存储在数组中。0<=heap_size<=heap_length

void max_heapify(int *a, int i) {             //O(lgn), 维护heap的性质，使得以下标i为根结点的子树重新遵循最大堆的性质
	int l = left(i), r = right(i);
	int largest = 0;
	if (l < heap_size && a[l] > a[i])
		largest = l;
	else
		largest = i;
	if (r < heap_size && a[r] > a[largest])
		largest = r;
	if (largest != i) {
		swap(a[i], a[largest]);
		max_heapify(a, largest);
	}
}

void build_max_heap(int *a) {             //O(n), 对树中非叶结点都调用一次 max_heapify
	heap_size = heap_length;
	for (int i = heap_length/2 - 1; i >= 0; --i)   //可以证明下标为n/2-1到0的结点为非叶结点
		max_heapify(a, i);
}


int heap_maximum(int *A) {
	return A[0];
}

int heap_extract_max(int *A) {
//	if (heap_size < 1)
//		return;
	int max = A[0];
	A[0] = A[heap_size-1];
	--heap_size;
	max_heapify(A, 0);
	return max;
}

void heap_increase(int *A, int i, int key) {
	if (key < A[i])
		return;
	A[i] = key;
	while (i > 0 && A[parent(i)] < A[i]) {
		swap(A[i], A[parent(i)]);
		i = parent(i);
	}
}

void max_heap_insert(int *A, int key) {
	++heap_size;
	A[heap_size-1] =  INT_MIN;
	heap_increase(A, heap_size-1, key);
}

bool empty() {
	return heap_size == 0;
}
int main()
{
	srand(time(NULL));
	while (scanf("%d", &heap_length) != EOF) {
		int a[heap_length];
		for (int i = 0; i < heap_length; ++i)
			a[i] = rand() % heap_length;
		build_max_heap(a);                           //构建最大堆
		while (!empty()) {
			printf("%d ", heap_extract_max(a));
		}
		printf("\n");
	}
	return 0;
}

C++最大堆实现priority_queue优先级队列（算法导论）,布布扣,bubuko.com

C++最大堆实现priority_queue优先级队列（算法导论）

原文：http://blog.csdn.net/pegasuswang_/article/details/21045315