笔者近日实现了最小堆类及其派生的优先级队列,特将代码奉上,不足之处还请指出!
在实现优先级队列时,笔者表示萌萌哒没有用过template写派生类,结果写完了出现error: *** was not decleared in this scope。。后来各种补上this->才完事,在CSDN(笔者的帖子地址☞ http://bbs.csdn.net/topics/391806995)上提问后才知道是模板参数依赖,笔者表示涨姿势了。。
/**
* The Minimum Heap Class and Heap Sort in C++
* Thanks to Introduction to Algorithms (CLRS) Chapter 6
* Thanks to Tsinghua MOOC of "Data Structure and Algorithms"
* Author: Zheng Chen / Arclabs001
* Email : chenzheng17@yahoo.com
* Copyright 2015 Xi'an University of Posts & Telecommunications. All rights reserved.
*/
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#define INF 0xFFFFFFF
using namespace std;
template<class T>
class Min_Heap
{
private:
vector<T> A;
int _size; //The size of heap
int parent(int i) { return (i-1)/2; } //Get the index of ith parent
int left(int i) { return 2*i+1; } //Get the index of ith left child
int right(int i) { return 2*i+2; } //Get the index of ith right child
public:
//Here are three different constructor
Min_Heap() {A.clear(); A.reserve(100); _size=0;}
Min_Heap(vector<T> _array)
{
_size = 0;
A.clear(); A.reserve(_array.size()*2);
for(int i=0; i<_array.size(); i++)
{
A.insert(A.end(), _array[i]);
_size++;
}
for(int i=(_size-1)/2; i>=0; i--)
{
Min_Heapify(i);
}
}
Min_Heap(T* _array, int array_size)
{
_size = 0;
A.clear(); A.reserve(array_size*2);
for(int i=0; i<_size; i++)
{
A.insert(A.end(), _array[i]);
_size++;
}
for(int i=(_size-1)/2; i>=0; i--)
{
Min_Heapify(i);
}
}
void Min_Heapify(int i)
{
int smallest;
int l = left(i);
int r = right(i);
if(l<_size && A[l]<A[i]) smallest = l;
else smallest = i;
if(r<_size && A[r]<A[smallest]) smallest = r;
if(smallest != i)
{
swap(A[i],A[smallest]);
Min_Heapify(smallest);
}
}
//The Heap Sort function
//Final status : The array A's element in desending order.
void sort()
{
for(int i=_size-1; i>0; i--)
{
swap(A[0],A[i]);
--_size;
Min_Heapify(0);
}
}
T& pop()
{
--_size;
T *tmp = new T;
*tmp = A[0];
swap(A[0],A[_size]);
Min_Heapify(0);
return *tmp;
}
void push(const T &key)
{
A.insert(A.end(),INF);
_size++;
int i = _size-1;
while(i>0 && key < A[parent(i)])
{
A[i] = A[parent(i)];
i = parent(i);
}
A[i] = key;
}
void _delete(int i) //delete the ith element
{
swap(A[i],A[_size-1]);
--_size;
A.erase(A.begin()+_size);
Min_Heapify(i);
}
bool decrease_key(int i, const T &key)
{
if(key > A[i])
{
return false;
}
while(i>0 && key < A[parent(i)])
{
A[i] = A[parent(i)];
i = parent(i);
}
A[i] = key;
return true;
}
void showHeap()
{
for(int i=0; i<_size; i++)
{
cout<<A[i]<<" ";
}
cout<<endl;
}
void showAll()
{
for(int i=0; i<A.size(); i++)
{
cout<<A[i]<<" ";
}
cout<<endl;
}
};
int main()
{
vector<int> A;
A.clear();
A.reserve(20);
srand((unsigned int)time(0));
for(int i=0; i<10; i++)
A.insert(A.end(),rand()%1000);
Min_Heap<int> heap(A);
heap.showHeap();
heap.decrease_key(5,0);
heap.showHeap();
heap.sort();
heap.showAll();
heap._delete(3);
heap.showAll();
return 0;
}
这个是优先级队列:
/**
* The Priority Queue Class in C++
* Thanks to Introduction to Algorithms (CLRS) Chapter 6
* Author: Zheng Chen / Arclabs001
* Email : chenzheng17@yahoo.com
* Copyright 2015 Xi'an University of Posts & Telecommunications. All rights reserved.
*/
#include "myheap.h"
#define INF 0xFFFFFFF
using namespace std;
template <class T>
class Priority_Queue: public Min_Heap<T>
{
public:
Priority_Queue(): Min_Heap<T>() {}
Priority_Queue(vector<T> _array):Min_Heap<T>(_array) {}
Priority_Queue(T *_array, int array_size): Min_Heap<T>(_array, array_size) {}
T& minimum() {return this->A[0];}
T& pop()
{
--this->_size;
T *tmp = new T;
*tmp = this->A[0];
swap(this->A[0],this->A[this->_size]);
this->Min_Heapify(0);
return *tmp;
}
bool decrease_key(int i, const T &key)
{
if(key > this->A[i])
{
return false;
}
this->A[i] = key;
while(i>0 && this->A[i]<this->A[this->parent(i)])
{
swap(this->A[i],this->A[this->parent(i)]);
i = this->parent(i);
}
return true;
}
void push(const T &key)
{
this->A.insert(this->A.end(),INF);
this->_size++;
int i = this->_size-1;
while(i>0 && key < this->A[this->parent(i)])
{
this->A[i] = this->A[this->parent(i)];
i = this->parent(i);
}
this->A[i] = key;
}
};
int main()
{
vector<int> A;
A.clear();
A.reserve(20);
srand((unsigned int)time(0));
for(int i=0; i<10; i++)
A.insert(A.end(),rand()%1000);
Priority_Queue<int> pq(A);
pq.show();
pq.push(rand()%1000);
pq.show();
pq.pop();
pq.show();
pq.decrease_key(5,0);
pq.show();
return 0;
}