Sorting

Max heap priority queue

Pinterest LinkedIn Tumblr

Priority queues insert the largest key value at the front of the queue (max heap). Write a program to implement max heap priority queue.

source Code

package com.dsacode.Algorithm.sorting;
 
import java.util.Arrays;
 
public class MaxheapPriorityqueue {
 
    private Integer[] mArray;
    private int mHeapSize;
 
    public MaxheapPriorityqueue(int maxSize) {
        mArray = new Integer[maxSize];
        mHeapSize = 0;
    }
 
    int parentIndex(int i) {
        return (i + 1) / 2 - 1;
    }
 
    int leftChildIndex(int i) {
        return 2 * i + 1;
    }
 
    int rightChildIndex(int i) {
        return 2 * i + 2;
    }
 
    void maxHeapify(int i) {
        int leftChildIndex = leftChildIndex(i);
        int rightChildIndex = rightChildIndex(i);
        int largestElementIndex;
        if (leftChildIndex < mHeapSize && mArray[leftChildIndex] > mArray[i]) {
            largestElementIndex = leftChildIndex;
        } else {
            largestElementIndex = i;
        }
        if (rightChildIndex < mHeapSize
                && mArray[rightChildIndex] > mArray[largestElementIndex]) {
            largestElementIndex = rightChildIndex;
        }
        if (largestElementIndex != i) {
            int tmpValue = mArray[i];
            mArray[i] = mArray[largestElementIndex];
            mArray[largestElementIndex] = tmpValue;
            maxHeapify(largestElementIndex);
        }
    }
 
    void buildMaxHeap() {
        int heapSize = mArray.length;
        for (int i = heapSize / 2; i >= 0; i--) {
            maxHeapify(i);
        }
    }
 
    public int max() {
        return mArray[0];
    }
 
    public int extractMax() {
        int max = mArray[0];
        mArray[0] = mArray[mHeapSize - 1];
        mArray[mHeapSize - 1] = null;
        mHeapSize--;
        maxHeapify(0);
        return max;
    }
 
    void increaseKey(int i, int newValue) throws Exception {
        if (newValue < mArray[i]) {
            throw new Exception("New value is smaller than current value");
        }
        mArray[i] = newValue;
        while (i > 0 && mArray[parentIndex(i)] < mArray[i]) {
            int tmpValue = mArray[parentIndex(i)];
            mArray[parentIndex(i)] = mArray[i];
            mArray[i] = tmpValue;
            i = parentIndex(i);
        }
    }
 
    public boolean insert(int value) {
        if (mHeapSize < mArray.length) {
            mHeapSize++;
            mArray[mHeapSize - 1] = value;
            try {
                increaseKey(mHeapSize - 1, value);
            } catch (Exception e) {
                return false;
            }
            return true;
        } else {
            return false;
        }
    }
 
    public int size() {
        return mHeapSize;
    }
 
    public String toString() {
        String string = "";
        for (int i = 0; i < mHeapSize; i++) {
            string += mArray[i] + " ";
        }
        return string;
    }
 
    public static void main(String[] args) {
 
        Integer[] array = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
        System.out.println("Array of items for insert Priority Queue: "
                + Arrays.toString(array));
        MaxheapPriorityqueue heap = new MaxheapPriorityqueue(100);
        for (int i : array) {
            heap.insert(i);
        }
 
        System.out.println("Itmes from Priority Queue: " + heap.toString());
 
        System.out
                .print("Itmes from Priority Queue extracted using Max items: ");
        int heapSize = heap.size();
        for (int i = 0; i < heapSize; i++) {
            System.out.print(heap.extractMax() + " ");
        }
        System.out.println();
 
    }
 
}

Output

Array of items for insert Priority Queue: [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
Itmes from Priority Queue: 16 14 10 8 7 3 9 1 4 2
Itmes from Priority Queue extracted using Max items: 16 14 10 9 8 7 4 3 2 1 

Algorithm Explanation

Insert an item into priority queue based on the priority.
Let r is the data at the top of the heap and t is the node at the top of the heap.
Replace t with the node at the lowest, farthest right position.
Heapify the whole tree and return r.

Reference

  1. http://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/studio122.html
  2. http://www.cs.mcgill.ca/~cs203/lectures/lecture10/sld024.htm

Write A Comment