//heapsort 2 //heaps2.cpp #include typedef int itemType; void swap(itemType a[], int p, int q); class PQ { private: int *a, *p, *info; int N; public: PQ(int size) { a = new itemType[size]; p = new itemType[size]; info = new int[size]; N=0; } ~PQ() { delete a; delete p; delete info; } void insert(int x, itemType v) { a[++N] = v; p[x] = N; info[N]=x; } void change(int x, itemType v) { a[p[x]] = v; } int remove() { // remove smallest int j, min = 1; for (j=2; j<=N; j++) if (a[j] < a[min]) min=j; swap(a, min, N); swap(info, min, N); p[info[min]]=min; return info[N--]; } int empty() { return (N <= 0); } }; void swap(itemType a[], int p, int q) { itemType t = a[p]; a[p] = a[q]; a[q] = t; } void main() { PQ heap(10); heap.insert(2,1); heap.insert(3,2); heap.insert(9,3); heap.insert(12,4); cout << heap.remove() << " " << heap.remove() << " "; cout << heap.remove() << " " << heap.remove(); }