用C++实现的最大堆代码,C代码库,德仔网

代码语言

代码分类

【C】用C++实现的最大堆

作者:chenkaiss / 发布于2013/10/23/ 688


	#ifndef __MAXHEAP_H_
	#define __MAXHEAP_H_

	namespace jc {
	namespace forwork {
	 class MaxHeap {
	 private:
	 int *container;
	 int size;
	 private:
	 void FixUp() {
	 int p = (size - 2) / 2; //父结点位置
	 int cur = size - 1; //当前结点位置
	 while(cur > 0) {
	 if(container[cur] > container[p]) {
	 swap(container[cur], container[p]);
	 cur = p;
	 p = (cur - 1) / 2;
	 } else break;
	 }
	 }
	 void FixDown() {
	 int c = 0, cl = c * 2 + 1;
	 if(c == size - 1) return;
	 while(true) {
	 if(cl + 1 <= size - 1) {
	 if(container[cl + 1] > container[cl]) cl += 1;
	 }
	 if(container[cl] > container[c]) {
	 swap(container[cl], container[c]);
	 c = cl;
	 cl = c * 2 + 1;
	 if(c >= size - 1) break;
	 } else break;
	 }
	 }
	 public:
	 MaxHeap() : size(0) {
	 this->container = new int[INT_MAX / 100];
	 }
	 ~MaxHeap() {
	 delete []container;
	 }
	 void Display() {
	 for(int i = 0; i < this->size; ++i) cout << container[i] << " ";
	 cout << endl;
	 }
	 int GetHead() {
	 if(size <= 0) throw exception("the heap is empty");
	 return this->container[0];
	 }
	 void Add(int value) {
	 container[size++] = value;
	 FixUp();
	 }
	 bool IsEmpty() {
	 return size == 0;
	 }
	 int Delete() {
	 if(size == 0) throw exception("the heap is empty");
	 else {
	 int ret = container[0];
	 container[0] = container[--size];
	 this->FixDown();
	 return ret;
	 }
	 }
	 void MakeHeap(int *items, int n) {
	 for(int i = 0; i < n; ++i) {
	 container[size++] = items[i];
	 FixUp();
	 }
	 }
	 };
	}
	}

	#endif

试试其它关键字

　最大堆　

同语言下

可能有用的

chenkaiss贡献的其它代码(1)

.用C++实现的最大堆