[编程珠玑读书笔记]优先队列

以前学数据结构的时候，学到后面一些抽象一点的数据结构，老师也不让我们写代码，也没有强调这些东西的重要性。再加上那时候不懂事，都没有具体去实现过堆，总认为这是很复杂的东西，其实学会以后真是简单的不得了，而且是又简单，又好用。#include<iostream> #include<stdlib.h> #include<stdio.h> using namespace std; template<class T> class priqueue{ private: int n,maxsize; T *x; void swap( int i, int j) { T t = x[i]; x[i] = x[j]; x[j] = t; } public: priqueue( int m) { maxsize = m; x = new T[maxsize + 1]; n = 0; } void insert( T t) { int i, p; x[++n] = t; //插入新元素到小根堆，将自己的值和父亲的值做比较 for( i = n; i > 1 && x[ p = i / 2] > x[i]; i= p) swap( p, i); } T extractmin() { int i,c; //提取最小的元素，也就是第一个元素，再将最后一个元素放在第一个的位置，然后向下移动，保持小根堆 T t = x[1]; x[1] = x[ n-- ]; for( i = 1; ( c = 2 * i ) <= n; i = c) { if( c + 1 <= n && x[ c + 1 ] < x[c]) c++; if( x[i] <= x[c] ) break; swap( c, i); } return t; } }; int main() { srand(5); int i; priqueue<int> queue( 20 ); for( i = 0; i < 20; i++) queue.insert( rand() % 500 ); for( i = 0; i < 20; i++) cout << queue.extractmin() << "\t"; cout << endl; return 0; }

编程珠玑书本实例：