template<typename T>
class MinPQ {
public:
MinPQ(int _cap);
~MinPQ();
public:
void insert(T val);
void deletTop();
T getTop();
int size; //数组长度为size，最大下标为size-1
inline int getCapacity();
void printall(); //测试用，打印数组所有元素
private:
void swim(int index);
void sink(int index);
void resize(int max); //动态调整数组大小
private:
int capacity;
T *heap;
};
template<typename T>
MinPQ<T>::MinPQ(int _cap)
:capacity(_cap), size(0) {
heap = new T[capacity];
}
template<typename T>
void MinPQ<T>::sink(int k) {
while (2*k + 1 <= size - 1) { // 存在左子节点,进入循环 验证
int lhs = 2*k + 1;
if (lhs < size-1 && heap[lhs + 1] < heap[lhs]) // lhs<size-1的作用是防止lhs==size-1，那就没有右节点了
++lhs; // 因为是最小堆，所以取左右节点较小的
if (heap[k] < heap[lhs]) // 当k这个根节点满足小于左右节点的时候 k已经在它该在的位置了 break
break;
swap(heap[k], heap[lhs]);
k = lhs;
}
}
template<typename T>
void MinPQ<T>::swim(int k) {
while (k > 0 && heap[(k - 1) / 2] > heap[k]) {
swap(heap[k], heap[(k - 1) / 2]);
k = (k - 1) / 2;
}
}
template<typename T>
int MinPQ<T>::getCapacity() {
return capacity;
}
template<typename T>
void MinPQ<T>::resize(int max) {
T *tmp = new T[max];
capacity = max; //不要忘记更新capacity
for (int i = 0; i != size; ++i)
tmp[i] = heap[i];
delete[]heap; //不要忘记 delete之前的 防止内存泄漏
heap = tmp;
}
template<typename T>
void MinPQ<T>::insert(T val) {
if (size == capacity) resize(size * 2);
heap[size] = val;
swim(size);
++size;
}
template<typename T>
void MinPQ<T>::deletTop() {
swap(heap[size - 1], heap[0]);
--size;
if (size > 0 && size == capacity / 4)
resize(capacity / 2);
sink(0); //注意一定要先 变size 再sink 因为sink里面涉及到了size
}
template<typename T>
T MinPQ<T>::getTop() {
return heap[0];
}
template<typename T>
MinPQ<T>::~MinPQ() {
delete[]heap;
}
template<typename T>
void MinPQ<T>::printall() {
for (int i = 0; i != size; ++i)
cout << heap[i] << " ";
cout << endl;
}
int main() {
MinPQ<int> test(3);
for (int i = 10,j=1; i != 0; --i,++j) {
test.insert(i*i);
cout << "第 " << j << "次,插入 " << i*i << endl;
cout << "Top: " << test.getTop() << endl;
cout << "size: " << test.size << endl;
cout << "capacity: " << test.getCapacity() << endl;
test.printall();
cout << endl;
}
for (int i = 1; i != 8; ++i) {
test.deletTop();
cout << "第 " << i << "次，删除 " << endl;
cout << "Top: " << test.getTop() << endl;
cout << "size: " << test.size << endl;
cout << "capacity: " << test.getCapacity() << endl;
test.printall();
cout << endl;
}
system("pause");
}
| 
转播
