What changes should I make to my maximum heap-based priority queue, that is max. value is on root, to be minimum heap-based priority queue, that is min. value on top ??
Below is codes my for maximum heap-based:
Below is codes my for maximum heap-based:
Code:
#ifndef HEAPH
#define HEAPH
#include<iostream>
#include<cassert>
using namespace std;
//==============================================================
// Heap Class Declaration
//==============================================================
class Heap{
int* array;
int size;
/* Gets the parent of an index/node of the heap
Pre-condition: no parent for root node
Post-condition: parent of an index is returned
*/
int parent(int);
/* Gets the left child of an index/node of the heap
Pre-condition: none
Post-condition: left child of an index is returned
*/
int leftchild(int);
/* Gets the right child of an index/node of the heap
Pre-condition: none
Post-condition: right child of an index is returned
*/
int rightchild(int);
public:
/* Creates a heap and initializes it with the integer array parameter.
Pre-condition: none
Post-condition: Every element in array maintains the heap property
*/
virtual void create(int*, int);
/* Creates an empty heap
Pre-condition: none
Post-condition: Every element in array maintains the heap property
*/
virtual void create();
/* Maintains the heap property : every parent is greater than its children.
Pre-condition: none
Post-condition: every parent is greater than its children
*/
virtual void heapify(int*, int);
/* Sorts the array parameter with its size using the HeapSort algorithm.
Pre-condition: array is an array of integers
Post-condition: array is sorted in ascending order
*/
virtual void sort(int*, int);
/* Inserts key into the heap.
Pre-condition: none
Post-condition: the heap contains key in the appropriate place
*/
virtual void heapInsert(int);
/* Removes the largest key from the heap and returns it. Return
-1 if nothing is in the heap
Pre-condition: none
Post-condition: The largest key has been removed from the heap
*/
virtual int extractMax();
/* Returns the largest key from the heap, but does not remove it
Pre-condition: none
Post-condition: none
*/
virtual int getMax();
/* Displays the heap with all its elements
Pre-condition: none
Post-condition: all elements are printed correctly
*/
virtual void print();
};
//==============================================================
// Heap Class Functions Definitions
//==============================================================
// Get parent of index
int Heap::parent(int index){
assert(index != 0);
return (index - 1)/2;
}
// Get left child of an index
int Heap::leftchild(int index){
return (index*2) + 1;
}
// Get right child of an index
int Heap::rightchild(int index){
return (2*index)+2;
}
// Creates a heap and initializes it with the integer array parameter.
void Heap::create(int* a, int aSize){
array = new int[aSize];
size = aSize;
for (int i = 0; i < aSize; ++i)
array[i] = a[i];
for(int i = (size-1)/2; i >= 0; --i)
heapify(array, i);
}
// Creates an empty heap
void Heap::create(){
array = new int[100];
size = 0;
}
// Guarantees heap property
void Heap::heapify(int* a, int index){
int l = leftchild(index);
int r = rightchild(index);
int largest;
if (l <= (size-1) && a[l] > a[index])
largest = l;
else largest = index;
if (r <= (size-1) && a[r] > a[largest])
largest = r;
if (largest != index){
int temp;
temp = a[index];
a[index] = a[largest];
a[largest] = temp;
heapify(a, largest);
}
}
// Sorts the array parameter using the HeapSort algorithm.
void Heap::sort(int*a, int aSize){
for(int i = (aSize-1)/2; i >= 0; --i)
heapify(a, i);
for (int i = size-1; i >= 0; i--){
int temp;
temp = array[0];
array[0] = array[i];
array[i] = temp;
size--;
heapify(array, 0);
}
size = aSize;
for(int i = 0; i < aSize; ++i){
a[i]= array[i];
cout << a[i] << " ";
}
cout<<endl;
}
// Inserts key into the heap.
void Heap::heapInsert(int key){
size++;
int i = size-1;
while (i > 0 && parent(i) > key){
array[i] = array[parent(i)];
i = parent(i);
}
array[i]= key;
for(int i = (size-1)/2; i >= 0; --i)
heapify(array, i);
}
// Removes the largest key from the heap and returns it
int Heap::extractMax(){
if (size == 0)
return -1;
else {
int max = array[0];
array[0] = array[size-1];
size--;
heapify(array, 0);
return max;
}
}
// Returns the largest key from the heap, but does not remove it
int Heap::getMax(){
return array[0];
}
// display the elements contained in heap
void Heap::print(){
for(int i = 0; i < size; ++i)
cout << array[i] << " ";
cout<<endl;
}
#endif
#ifndef PRIORITYQUEUEH
#define PRIORITYQUEUEH
#include<iostream>
#include "heap.h"
using namespace std;
//==============================================================
// Priority Queue Declaration
//==============================================================
class PriorityQueue:virtual public Heap{
int* array;
int size;
public:
/* inserts key into the priority queue.
Pre-condition: none
Post-condition: the priority queue contains key
*/
void enqueue(int);
/* removes the largest key from the priority queue and returns it. Return
-1 if nothing is in the queue
Pre-condition: none
Post-condition: The largest key has been removed from the queue
*/
int dequeue();
/* returns the largest key from the priority queue, but does not remove it
Pre-condition: none
Post-condition: none
*/
int peek();
};
//==============================================================
// Priority Queue Functions Definitions
//==============================================================
// inserts key into the priority queue.
void PriorityQueue::enqueue(int key){
heapInsert(key);
}
// removes the largest key from the priority queue and returns it
int PriorityQueue::dequeue(){
return extractMax();
}
// returns the largest key from the priority queue, but does not remove it
int PriorityQueue::peek(){
return getMax();
}
#endif
riority_queue