12.4. One problem with implementing a priority queue with an array-based heap is

Question

12.4. One problem with implementing a priority queue with an array-based heap is
the fixed size of the array. If your data outgrows the array, you’ll need to
expand the array, as we did for hash tables in Programming Project 11.4 in
Chapter 11, “Hash Tables.” You can avoid this problem by implementing a
priority queue with an ordinary binary search tree rather than a heap. A tree
can grow as large as it wants (except for system-memory constraints).
Start with the Tree class from the tree.java program (Listing 8.1). Modify this
class so it supports priority queues by adding a removeMax() method that
removes the largest item. In a heap this is easy, but in a tree it’s slightly harder.
How do you find the largest item in a tree? Do you need to worry about both
its children when you delete it? Implementing change() is optional. It’s easily
handled in a binary search tree by deleting the old item and inserting a new
one with a different key.
The application should relate to a PriorityQ class; the Tree class should be
invisible to main() (except perhaps for displaying the tree while you’re debug-
ging). Insertion and removeMax() will operate in O(logN) time.

Explanation / Answer

// A C++ program to demonstrate common Binary Heap Operations
#include<iostream>
#include<climits>
using namespace std;

// Prototype of a utility function to swap two integers
void swap(int *x, int *y);

// A class for Min Heap
class MinHeap
{
int *harr; // pointer to array of elements in heap
int capacity; // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
public:
// Constructor
MinHeap(int capacity);

// to heapify a subtree with root at given index
void MinHeapify(int );

int parent(int i) { return (i-1)/2; }

// to get index of left child of node at index i
int left(int i) { return (2*i + 1); }

// to get index of right child of node at index i
int right(int i) { return (2*i + 2); }

// to extract the root which is the minimum element
int extractMin();

// Decreases key value of key at index i to new_val
void decreaseKey(int i, int new_val);

// Returns the minimum key (key at root) from min heap
int getMin() { return harr[0]; }

// Deletes a key stored at index i
void deleteKey(int i);

// Inserts a new key 'k'
void insertKey(int k);
};

// Constructor: Builds a heap from a given array a[] of given size
MinHeap::MinHeap(int cap)
{
heap_size = 0;
capacity = cap;
harr = new int[cap];
}

// Inserts a new key 'k'
void MinHeap::insertKey(int k)
{
if (heap_size == capacity)
{
cout << " Overflow: Could not insertKey ";
return;
}

// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
harr[i] = k;

// Fix the min heap property if it is violated
while (i != 0 && harr[parent(i)] > harr[i])
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}

// Decreases value of key at index 'i' to new_val. It is assumed that
// new_val is smaller than harr[i].
void MinHeap::decreaseKey(int i, int new_val)
{
harr[i] = new_val;
while (i != 0 && harr[parent(i)] > harr[i])
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}

// Method to remove minimum element (or root) from min heap
int MinHeap::extractMin()
{
if (heap_size <= 0)
return INT_MAX;
if (heap_size == 1)
{
heap_size--;
return harr[0];
}

// Store the minimum value, and remove it from heap
int root = harr[0];
harr[0] = harr[heap_size-1];
heap_size--;
MinHeapify(0);

return root;
}


// This function deletes key at index i. It first reduced value to minus
// infinite, then calls extractMin()
void MinHeap::deleteKey(int i)
{
decreaseKey(i, INT_MIN);
extractMin();
}

// A recursive method to heapify a subtree with root at given index
// This method assumes that the subtrees are already heapified
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}

// A utility function to swap two elements
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}

// Driver program to test above functions
int main()
{
MinHeap h(11);
h.insertKey(3);
h.insertKey(2);
h.deleteKey(1);
h.insertKey(15);
h.insertKey(5);
h.insertKey(4);
h.insertKey(45);
cout << h.extractMin() << " ";
cout << h.getMin() << " ";
h.decreaseKey(2, 1);
cout << h.getMin();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.