↞↞Previous ↞Stack Data Structure

What is Queue?

You must have seen people line up in a bank to be served by a teller or at a Train ticket counter to get the ticket. This is always a fair practice which we follow in our real life. Queues maintain first-in, first-out order (FIFO). The FIFO property of a queue makes it similar like a line of customers waiting to get the tickets. We use Queue when order of retrieval should be the same as the order of insertion. Queues are often described in terms of producers and consumers. A producer is anything that stores data in a queue, while a consumer is anything that retrieves data from a queue.
Operations on a queue:

• Enqueue(x): Insert item x at the back of queue.
• Dequeue(): Return (and remove) the front item from queue.
• peek(): Return the front item of queue.
• Full(): Test whether the more items can be enqueued to the Queue.
• Empty(): Test whether the more items can be dequeued from the Queue.

Implementation of Queue Data Structure:

1. Implement using simple array. (bounded)
2. Implement using linked list. (unbounded)

Queues are little more difficult to implement than stacks, because action happens at both ends. Queue maintain indices to the first (front) and last (rear) elements in the array. We always enqueue an element at the rear of the queue, just as a newly arriving customer takes a place at the end of the line. The element dequeued is always the one at the front of the queue, like the customer at the head of the line who has waited the longest.

When you insert a new item in the queue in the Queue, the Front arrow moves upward, toward higher numbers in the array. When you remove an item, Rear also moves upward. The problem with this arrangement is that pretty soon the rear of the queue is at the end of the array. Even if there are empty cells at the beginning of the array, because you have removed them with dequeue, you still can’t insert a new item because Rear can’t go any further.

To avoid the problem of not being able to insert more items into the queue even when it’s not full, the Front and Rear arrows wrap around to the beginning of the array. The result is a circular queue.

Queue implementation in Java using Array

public class Queue {

	private int maxSize;
	private int queueArray[];
	private int front;
	private int rear;
	private int nItems;

	public Queue(int size) {
		maxSize = size;
		queueArray = new int[size];
		front = 0;
		rear = -1;
		nItems = 0;
	}

	public void enqueue(int value) {
		if(isFull()){
			System.err.println("Error: queue is full...");
			return;
		}
		if (rear == maxSize - 1) {
			rear = -1;
		}
		queueArray[++rear] = value;
		++nItems;
	}

	public int dequeue() {
		if(isEmpty()){
			System.err.println("Error: queue is empty...");
			return -1;
		}
		int temp = queueArray[front++];
		if (front == maxSize ) {
			front = 0;
		}
		nItems--;
		return temp;
	}
	
	public int peek(){
		return queueArray[front];
	}
	
	public boolean isEmpty(){
		return nItems==0;
	}
	
	public boolean isFull(){
		return nItems == maxSize;
	}
	public int size(){
                return nItems;
        }
	public static void main(String[] args) {
		Queue queue = new Queue(5);
		queue.enqueue(10);
		queue.enqueue(20);
		queue.enqueue(30);
		queue.enqueue(40);
		queue.enqueue(50);
		
		queue.dequeue();
		queue.dequeue();
		
		queue.enqueue(110);
		queue.enqueue(120);
		
		while(!queue.isEmpty()){
			System.out.print(queue.dequeue()+" ");
		}
	}
}
Output
----------
30 40 50 110 120 

Queue implementation in Java using Linked List

Create a Node class which will hold value and link to the next element.

public class Node {

	private int value;
	private Node next;
	
	public Node(int value) {
		this.value = value;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}
}

Create the Queue with all the methods.

public class Queue {
	private Node front;
	private Node rear;
        private int nItems;

	public Queue() {
		front = null;
		rear = null;
	}

	public boolean isEmpty() {
		return front == null;
	}

	public void enqueue(int value) {
		Node newNode = new Node(value);
		if (isEmpty()) {
			front = newNode;
		} else {
			rear.setNext(newNode);
		}
		rear = newNode;
                nItems++;
	}
	
	public int dequeue(){
		int val = front.getValue();
		if(front == rear){
			front = null;
			rear = null;
		}else{
			front= front.getNext();
		}
                nItems--;
		return val;
	}
	
	public void displayList(){
		Node current = front;
		while(current != null){
			System.out.print(current.getValue()+" ");
			current = current.getNext();
		}
		System.out.println();
	}
	
        public int size(){
              nItems;
        }
	public static void main(String[] args) {
		Queue queue = new Queue();
		queue.enqueue(10);
		queue.enqueue(20);
		queue.enqueue(30);
		queue.enqueue(40);
		queue.enqueue(50);
		
		queue.dequeue();
		queue.dequeue();
		
		queue.enqueue(110);
		queue.enqueue(120);
		
		queue.displayList();
	}
}

Output
---------
30 40 50 110 120 

References:

• Introduction To Algorithm – CLRS.
• Algorithm Design Manual – Skiena
• Data Structure & Algorithms In Java – Robert Lafore

1. Stack Data Structure
2. Queue Data Structure
3. Questions on Stack And Queue

What is Stack?

Think Stack as naturally model piles of objects, for example the dinner plates. After a new plate is washed, it is pushed on the top of the stack. When serving food, a clean plate is popped off the stack. Here the plates don’t care which one to be used next that is one of most important reason to use Stack data structure.

Important points:

• Stack is a container where items are retrieved by last-in, first-out (LIFO) order.
• Stack is the right container to use when retrieval order doesn’t matter
• Stack order is important in processing any properly nested structure. This includes recursive calls, parenthesized formula such as postfix evaluation, and depth first search traversal in Graph etc.
• Stacks are very simple to implement.

Operations on a Stack:

• push(x): Insert item x at the top of stack.
• pop(): Return and remove the top element of stack.
• peek(): Return the top element of stack.
• full(): Test whether the more items can be pushed to the stack.
• empty(): Test whether the more items can be popped from the stack.

Implementation of Stack Data Structure:

1. Implement using simple array. (bounded)
2. Implement using linked list. (unbounded)

Stack using array: This is very easy to implement. Create an array to hold the Stack values. Maintain a top which will point to the currently pushed element. Initially the top will be -1.
When you push a value to the Stack, you increment the top by 1. When you pop a value from the stack, you return the top element and then decrement the top.
For example – consider below stack. Initially top were -1. Before pushing 5, increment top = top+1 –top= -1+1 =0, 5 is pushed to the Stack at 0th position. Similarly before pushing 10, top is incremented by 1 and became 0+1 =1 and 10 is pushed at 1^st position.

Stack implementation in Java using Array

public class Stack {

	private int maxSize;
	private int[] stackArray;
	private int top;
        
        //initialize stack
	public Stack(int size) {
		stackArray = new int[size];
		maxSize = size;
		top = -1;
	}

	public void push(int value) {
		if (isFull()) {
			System.err.println("Stack is full..");
			return;
		}
		stackArray[++top] = value;
	}
        //Return and remove top element
	public int pop() {
		if (!isEmpty()) {
			return stackArray[top--];
		} else {
			System.err.println("Stack is empty...");
			return -1;
		}
	}
	//Return top element
	public int peek() {
		if (!isEmpty()) {
			return stackArray[top];
		} else {
			System.err.println("Stack is empty...");
			return -1;
		}
	}

	public boolean isEmpty() {
		return top == -1;
	}

	public boolean isFull() {
		return top == maxSize;
	}

	public static void main(String[] args) {
		Stack stack = new Stack(10);
		for (int i = 0; i < 10; i++) {
			stack.push(i);
		}
		for (int i = 0; i < 10; i++) {
			System.out.print(stack.pop()+" ");
		}
	}
}

Output
---------
9 8 7 6 5 4 3 2 1 0 

Stack implementation in Java using Linked List

Create a Node class which will hold value and link to the next element.

public class Node {

	private int value;
	private Node next;
	
	public Node(int value) {
		this.value = value;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}
}

Create the Stack with all the methods.

package com.test.stack;

public class Stack {

	private Node top;
	private int size;

	public Stack() {
		top = null;
		size = 0;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return top == null;
	}

	public void push(int value) {
		Node node = new Node(value);
		node.setNext(top);
		top = node;
		size++;
	}

	public int pop() {
		if (isEmpty()) {
			System.err.println("Stack is empty");
		}
		Integer temp = top.getValue();
		top = top.getNext();
		size--;
		return temp;
	}

	public int peek() {
		if (isEmpty()) {
			System.err.println("Stack is empty");
		}
		return top.getValue();
	}

	public static void main(String[] args) {
		Stack stack = new Stack();
		for (int i = 0; i < 10; i++) {
			stack.push(i);
		}
		for (int i = 0; i < 10; i++) {
			System.out.print(stack.pop() + " ");
		}

	}
}

Output
---------
9 8 7 6 5 4 3 2 1 0 

Next  ↠Queue data structure ↠↠

References:

• Introduction To Algorithm – CLRS.
• Algorithm Design Manual – Skiena
• Data Structure & Algorithms In Java – Robert Lafore

I would highly recommend to read below posts before getting into questions on heap-

• Heap Data Structure
• Heap As Priority Queue

Questions On Heap

Let’s discuss some of the questions on heap which can be easily solved with the help of Heap.

Problem 1: Find the largest k numbers (in value) out of n numbers. For example, if given an array with ten numbers {1, 8, 9, 2, 10, 14, 3, 4, 7, 16 }, please return the largest five numbers 8, 10, 9, 14, 16.
This Question can also be asked as-
Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume that the computer memory can hold all one billion numbers.
If large numbers involved in problem – first try to solve the problem for smaller numbers.

The simple solution is to sort the n input numbers in descending order and get the first K numbers. Sorting will cost you O(nlogn) time. You can apply insertion sort for smaller number of elements.

We can achieve this in O(nlogk) time using minHeap (Parent is smaller than its children).

1. Create a Min Heap with the first K numbers.
2. For each remaining number, insert it in the Min Heap and then delete the minimum value from the heap.
3. The heap now contains the largest K numbers.
4. This algorithm is O(n log K), where K is the number of values we are looking for.

The Solution using MinHeap will work as follows.

• If the K is greater than the number of input elements- no need to do anything just return the elements
• Fill the Min Heap with K elements of input Array. For example if K=5 then the Min Heap will contain [1, 2, 9, 8, 10]. Now compare the Array[K+1] say N with top element of Min Heap, if N is greater than Heap top element- remove top element and insert N. Repeat the process up to Array.length. Finally you will have the Min Heap with K largest elements.

Let’s create a Min Heap:

public class MinHeap {
	private int[] heapArray;
	private int maxSize;
	private int heapSize;

	public MinHeap(int size) {
		heapSize = 0;
		maxSize = size;
		heapArray = new int[maxSize];
	}

	public int size() {
		return heapSize;
	}

	public int peek() {
		assert heapSize <= 0 : "heap underflow";
		return heapArray[0];
	}

	public int get(int i) {
		assert heapSize <= 0 : "heap underflow";
		return heapArray[i];
	}

	public void insertKey(int key) {
		assert heapSize > maxSize - 1 : "heap overflow";
		heapArray[heapSize] = key;
		trickleUp(heapSize++);
	}

	// child dominate- parent will be smaller than children, if not then swap
	private void trickleUp(int i) {
		int parent = (i - 1) / 2;
		while (i > 0 && heapArray[i] < heapArray[parent]) {
			int temp = heapArray[parent];
			heapArray[parent] = heapArray[i];
			heapArray[i] = temp;
			i = parent;
			parent = (i - 1) / 2;
		}
	}

	// Top will be always the minimum
	public int extractMin() {
		assert heapSize < 0 : "heap underflow";
		int min = heapArray[0];
		heapArray[0] = heapArray[--heapSize];
		minHeapify(0);
		return min;
	}

	// Parent is less than its children
	public void minHeapify(int i) {
		int smallest = i;
		while (smallest < heapSize / 2) {
			int left = (2 * i) + 1;
			int right = left + 1;
			if (left < heapSize && heapArray[left] < heapArray[i]) {
				smallest = left;
			}
			if (right < heapSize && heapArray[right] < heapArray[smallest]) {
				smallest = right;
			}
			if (smallest != i) {
				int temp = heapArray[i];
				heapArray[i] = heapArray[smallest];
				heapArray[smallest] = temp;
				i = smallest;
			} else {
				break;
			}
		}
	}
}

Create a class LargestNumbersFinder:

package com.test.heap;

class LargestNumbersFinder {

	public static int[] getLargestNumbers(int[] input, int k) {
		// if required number of largest items is less than the given
		// array, return array itself
		if (input.length <= k) {
			return input;
		}
		int[] output = new int[k];
		MinHeap minHeap = new MinHeap(input.length);
		// insert the array's K element to the minHeap
		for (int i = 0; i < input.length; i++) {
			if (minHeap.size() < k) {
				minHeap.insertKey(input[i]);
			} else {
				if (minHeap.peek() < input[i]) {
					minHeap.extractMin();
					minHeap.insertKey(input[i]);
				}
			}
		}
		// Heap contains top K maximum numbers
		for (int i = 0; i < minHeap.size(); i++) {
			output[i] = minHeap.get(i);
		}
		return output;
	}

	public static void main(String[] args) {
		int[] array = { 1, 8, 9, 2, 10, 14, 3, 4, 7, 16 };
		int[] output = LargestNumbersFinder.getLargestNumbers(array, 5);
		for (int key : output) {
			System.out.print(key + " ");
		}
	}
}

Output
---------
8 10 9 14 16 

If you are asked to find least k numbers then use Max Heap in similar fashion. Just change the condition if (maxHeap.getMax() > input[i])

Problem 2: You are given a set of integers in an unordered binary tree. Use an array sorting routine to transform the tree into a heap that uses a balanced binary tree as its underlying data structure.

This problem is very simple. You have an unordered binary tree means there is no specific relationship between parent and child like in Binary search tree.
One important property of sorted array is the it satisfy heap condition without calling heapify. If array is sorted in ascending order, it satisfy the Min Heap property and if sorted in Descending order, it satisfy the Max Heap property. You can give try- write some numbers on notepad in sorted order and see if it also satisfy heap condition or not.

Now in this problem, our job is to traverse the Binary tree and store it in an Array- then sort the array in ascending order – now we know that sorted array elements can be directly inserted to min heap. We have already seen that in Array if the parent index is i then left child will be at position 2*i+1 and right child will be at position 2*i+2. Using this relationship insert the array elements back to the Binary tree.

import java.util.Arrays;
import java.util.Comparator;

public class BinaryTreeToHeap {

	// PreOrder traversal
	public static int traverse(Node node, int count, Node[] nodeArray) {
		if (node == null){
			return count;
		}
		if( nodeArray != null ){
			nodeArray[count] = node;
		}
		count++;
		count = traverse(node.leftChild, count, nodeArray);
		count = traverse(node.rightChild, count, nodeArray);
		return count;
	}

	public static Node heapifyBinaryTree(Node root) {
		//We don't know the size of array
		int size = traverse(root, 0, null); 
		Node[] nodeArray = new Node[size];
		// Fill nodes into array
		traverse(root, 0, nodeArray); 
		// Sort array of nodes based on their values, using Comparator object
		Arrays.sort(nodeArray, new Comparator<Node>() {
			@Override
			public int compare(Node m, Node n) {
				int value1 = m.key, value2 = n.key;
				return (value1 < value2 ? -1 : (value1 == value2 ? 0 : 1));
			}
		});
		//Assign the left and right link to each node
		for (int i = 0; i < size; i++) {
			int left = 2 * i + 1;
			int right = left + 1;
			nodeArray[i].leftChild = left >= size ? null : nodeArray[left];
			nodeArray[i].rightChild = right >= size ? null : nodeArray[right];
		}
		return nodeArray[0]; // Return new root node
	}
}

Problem 3: Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

First let’s understand about Median
Median is nothing but the middle most element in a set or ordered data. The condition here is that the data should be sorted either in ascending or descending.

For Example:
CASE-I: If number of elements(N) in data set is ODD then the Median = ((N+1)/2)^th element in data set.
Data set = {2,5,8,9,10,12,18,20,24,28,26}
In above data set N = 11 which id ODD and (N+1)/2 = (11+1)/2 = 6, therefore Median= 6^th element = 12
CASE-II: If number of elements(N) in data set is EVEN then the Median = AVERAGE of (N/2)^th and ((N/2)+1))^th element in data set.
Data set = {2,5,8,9,10,12,18,20,24,28,26,30}
In above data set N = 12 which id EVEN and N/2 = 12/2 = 6 and (N/2)+1) = 6+1=7 therefore Median= Average of 6^th and 7^th elements = (12 + 18)/2 = 15

The above problem can be easily solved using two priority heaps: a max heap for the values below the median, and a min heap for the values above the median.

If both the heap size is equal then the Median will be the average of top element of MaxHeap and MinHeap, otherwise the Median will be the top element of larger heap.
When a new value arrives it is placed in the below heap if the value is less than or equal to the median, otherwise it is placed into the above heap. The heap sizes can be equal or the below heap has one extra. This constraint can easily be restored by shifting an element from one heap to the other. The median is available in constant time and updates are O(lg n).

Here I will use Java PriorityQueue collection since it doesn’t have size constraint.

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

public class MedianFinder {

	// By default priority queue is MinHeap in java
	private PriorityQueue<Integer> maxHeap, minHeap;

	private static final int INITIAL_CAPACITY = 10;

	public MedianFinder() {
		//Nothing to do for minHeap
		minHeap = new PriorityQueue<Integer>(INITIAL_CAPACITY);
		
		//To act like a max heap, reverse the default behavior with comparator 
		maxHeap = new PriorityQueue<>(INITIAL_CAPACITY,	new Comparator<Integer>() {
				   		@Override
				   		public int compare(Integer i1, Integer i2) {
				   			return (i1 > i2 ? -1 : (i1 == i2 ? 0 : 1));
				   		}
		  		  	});
	}

	public void addNewNumber(int randomNumber) {
		if (maxHeap.size() == minHeap.size()) {
			if ((minHeap.peek() != null) && randomNumber > minHeap.peek()) {
				maxHeap.offer(minHeap.poll());
				minHeap.offer(randomNumber);
			} else {
				maxHeap.offer(randomNumber);
			}
		} else {
			if (randomNumber < maxHeap.peek()) {
				minHeap.offer(maxHeap.poll());
				maxHeap.offer(randomNumber);
			} else {
				minHeap.offer(randomNumber);
			}
		}
	}

	public double getMedian() {
		if (maxHeap.isEmpty())
			return minHeap.peek();
		else if (minHeap.isEmpty())
			return maxHeap.peek();
		if (maxHeap.size() == minHeap.size()) {
			return (minHeap.peek() + maxHeap.peek()) / 2.0;
		} else if (maxHeap.size() > minHeap.size()) {
			return maxHeap.peek();
		} else {
			return minHeap.peek();
		}
	}

	//Generate some random numbers between 0 to 100
	private int[] generateRandomArray(int size) {
		int[] array = new int[size];
		Random random = new Random();
		for (int i = 0; i < size; i++) {
			array[i] = random.nextInt(100); // between 0 to 100
		}
		return array;
	}
	public static void main(String[] args) {
		MedianFinder medianFinder = new MedianFinder();
		
		//If the number(N) of elements is Odd then median = (N+1)/2 th element
                System.out.println("------N is ODD------");
		int[] A1 = medianFinder.generateRandomArray(15);
		System.out.println("Array: " + Arrays.toString(A1));
		for (int a : A1) {
			medianFinder.addNewNumber(a);
		}
		System.out.println("Median is: "+medianFinder.getMedian());
		//Try to find median in sorted array
		Arrays.sort(A1);
		System.out.println("Sorted Array: "+Arrays.toString(A1));
		
		// If the number(N) of elements is Even then median = AVG(N/2th, N/2th) element
                System.out.println("------N is EVEN------");
		medianFinder = new MedianFinder();
		int[] A2 = medianFinder.generateRandomArray(16);
		System.out.println("Array: " + Arrays.toString(A2));
		for (int a : A2) {
			medianFinder.addNewNumber(a);
		}
		System.out.println("Median is: " + medianFinder.getMedian());
		// Try to find median in sorted array
		Arrays.sort(A2);
		System.out.println("Sorted Array: " + Arrays.toString(A2));
	}
}

Output
--------
------N is ODD------
Array: [47, 35, 88, 25, 12, 75, 8, 53, 74, 18, 15, 51, 92, 4, 45]
Median is: 45.0
Sorted Array: [4, 8, 12, 15, 18, 25, 35, 45, 47, 51, 53, 74, 75, 88, 92]
------N is EVEN------
Array: [35, 59, 54, 41, 85, 71, 99, 30, 2, 67, 27, 18, 60, 87, 33, 2]
Median is: 47.5
Sorted Array: [2, 2, 18, 27, 30, 33, 35, 41, 54, 59, 60, 67, 71, 85, 87, 99]

Problem 4: Convert Max-Heap to Min-Heap or vice-versa.

This question I leave as an exercise for the reader. The logic is very simple- If you have to convert Max-Heap to Min-Heap – just call minHeapify(i) for i= (heapSize-1)/2 to 0. And for Min-Heap to Max-Heap call maxHeapify(i) in similar manner.

References:

• Cracking The Coding Interview- Gayle Laakmann McDowell
• Programming Interviews Exposed- John Mongan, Eric Giguère, Noah Kindler.
• Coding Interviews- Harry He

↞↞Previous ↞Heap Data Structure

Heap As Priority Queue

This part of tutorial is in continuation of previous post. Before reading this part I would highly recommend to go through first part(Heap Data Structure) of this tutorial.

What is Priority Queue
Many important applications require selection of an item of the highest priority among a dynamically changing set of items. A priority queue is an Abstract Data Type that offer the needs of such applications. For an example- Priority queues may be used for task scheduling in computers, where higher priority task runs first that lower priority tasks. Priority queue also used in some important algorithms of Graph like Prim’s algorithm and Dijkstra’s algorithm.

A priority queue offers methods that allow:

• get an item of highest priority
• removal an item with the highest priority
• inserting an item
• change an item

I already covered basics of Heap in details in my previous section. Let’s directly jump to the heap as priority queue. Here the heap will be represented in such a way that it will support all the above mentioned Priority queue methods. Here we will also see the TopDown or trickleUp heap construction algorithm.

import java.util.Arrays;

public class Heap {

	private int[] heapArray;
	private int maxSize;
	private int heapSize;

	public Heap(int size) {
		heapSize = 0;
		maxSize = size;
		heapArray = new int[maxSize];
	}
        public boolean isEmpty() {
		return heapSize == 0;
	}
        //insert at last position, if parent is smaller then swap 
        //with parent. Repeat the process until key is at its proper
        //position. 
        public void insertKey(int key) {
		assert heapSize > maxSize-1 : "heap overflow";
		heapArray[heapSize] = key;
		trickleUp(heapSize++);
	}
        private void trickleUp(int i) {
		int parent = (i - 1) / 2;
		while (i > 0 && heapArray[i] > heapArray[parent]) {
			int temp = heapArray[parent];
			heapArray[parent] = heapArray[i];
			heapArray[i] = temp;
			i = parent;
			parent = (i - 1) / 2;
		}
        }
        public int peek() {
		assert heapSize <= 0 : "heap underflow";
		return heapArray[0];
        }

        public int extractMax() {
		assert heapSize <= 0 : "heap underflow";
		int max = heapArray[0];
		heapArray[0] = heapArray[--heapSize];
		maxHeapify(0);
		return max;
       }
       public void changeKey(int i, int key) {
		int oldValue = heapArray[i];
		heapArray[i] = key;
		if(key > oldValue){
			trickleUp(i);
		}else{
			maxHeapify(i);
		}
       }
       public void maxHeapify(int i) {
		int largest = i;
		while (largest < heapSize/2) {
			int left = (2 * i) + 1;
			int right = left + 1;
			if (left < heapSize && heapArray[left] > heapArray[i]) {
				largest = left; // largest=6
			}
			if (right < heapSize && heapArray[right] > heapArray[largest]) {
				largest = right;
			}
			if (largest != i) {
				int temp = heapArray[i];
				heapArray[i] = heapArray[largest];
				heapArray[largest] = temp;
				i = largest;
			} else {
				break;
			}

		}
       }
       public void showHeap() {
		for (int i = 0; i < heapSize; i++) {
			System.out.print(heapArray[i] + ", ");
		}
		System.out.println();
       }
       public static void main(String[] args) {
		int[] A1 = { 1, 8, 9, 2, 10, 14, 3, 4, 7, 16 };
		
		System.out.println("Original Array:: "+Arrays.toString(A1));
		Heap heap = new Heap(10);
		for (int i : A1) {
			heap.insertKey(i);
		}
		System.out.print("After inserting to heap:: ");
		heap.showHeap();
		System.out.println();
		System.out.println("Removed Max:: " + heap.extractMax());
		System.out.println("Removed Max:: " + heap.extractMax());
		System.out.print("After two removal the heap:: ");
		heap.showHeap();
		System.out.println();
		heap.insertKey(50);
		heap.insertKey(0);
		System.out.print("After inserting 50 and 0 the heap:: ");
		heap.showHeap();
       }
}
Output
--------
Original Array:: [1, 8, 9, 2, 10, 14, 3, 4, 7, 16]
After inserting to heap:: 16, 14, 10, 7, 9, 8, 3, 1, 4, 2 
Removed Max:: 16
Removed Max:: 14
After two removal the heap:: 10, 9, 8, 7, 2, 4, 3, 1, 
After inserting 50 and 0 the heap:: 50, 10, 8, 9, 2, 4, 3, 1, 7, 0 

Let’s discuss each method in detail:
Remember array representation of a heap to understand the code.
insertKey() & trickleUp()
This is another method to create a Heap. It Is not as efficient as maxHeapify().
When you insert a key to the Heap, you always insert at the last position of the array. There may be the case that newly inserted key violate the Heap condition. Call trickleUp() to place this key at proper position. In trickleUp() you compare the new key to its parent – if the parent is smaller, swap the key with parent key. Repeat the process until you reach to the root(top) or the heap condition satisfied for this key. The running time of this method is O(logn), since the path traced from the insertion position to the root has length O(logn).

peek()
Top element of the array is the highest element. This method return first element. It takes O(1) time.

extracMax()
This method removes the largest element which is always at the top of array. First it gets the A[0] element – then it copies the A[n] to A[0] – now there may be the case that A[0] element violate the heap condition – call maxHeapify(0) to top element. This method takes O(logn) time since it works on the top root element and may move top to bottom equals to the height of the tree i.e O(logn).
changeKey()
This method change key at particular position. There are two possibilities here, either the changed key will be greater than the current key or it will be smaller than the current key. If it is greater then there may be the chance that it is greater than its parent , use trickleUp() to place it at proper position. If the changed key is smaller the current key, there may be the chance that that it is smaller than its children, use maxHeapify() to place it at proper position. This method running time is also proportional to its height i.e. O(logn).

Next  ↠Questions on Heap ↠↠

1. Heap Data Structure
2. Heap As Priority Queue
3. Questions on Heap

What is Heap Data Structure?

• Heap data structure is nowhere related to heap memory area referred in Programming language like C++ and Java.
• You can visualize it as a nearly complete binary tree. It is also referred as Binary heap.
• Each node in a heap should satisfy the below heap condition.
  • Max Heap: Parent node is always greater than its child. (parent dominates)
  • Min Heap: Parent node is always smaller than its child. (child dominates)
• It is a weakly or partially ordered (as compared to Binary Search Tree) data structure that is especially suitable for implementing priority queue.
• Never think of Heap as being sorted. It is not sorted at all. What makes a heap interesting is that the largest element is always on the top of a max heap.
• It can be represented through simple Array. Thank GOD there is no links.

Going forward Heap refers max heap only. MinHeap will be trivial if you understand MaxHeap clearly, you will just have to change some less than(<) and greater than(>) sign. I have implemented a min heap in question section.

What is a complete binary tree?
A complete binary tree is completely filled from left to right across each row with one possible exception that the last row need not be full; it is filled from the left up to a point.


Important properties of a complete binary tree:

• A complete binary tree of height h has 2^h+1−1 nodes.
• A complete binary tree of height h has 2^h−1 non-leaf nodes.
• A complete binary tree of height h has 2^h leaf nodes.
• A complete binary tree of height h has between 2^h and 2^h+1 – 1 node.
• A Heap tree height with n nodes is equal to ⌊log2ⁿ⌋.

It’s very easy to understand if you know the basics of Logrithms.
Let’s try to understand this:

In above complete binary tree we have 7 nodes which we can write as 2³-1.
2^h+1-1 => 2²⁺¹-1 = 7 (approximately we raised 2 to the height of the tree to get number of nodes)
When you write log2ⁿ means that how many times you will raise 2 to get n. For ex. Log2⁸ =3 => 2³=8.

Representation of a heap
A heap can be implemented as an array by recording its elements in the top-down, left-to-right fashion.

Important observations:

• Here you can see that a heap is a complete binary tree therefore there are no holes in the array used to represent it.
• The parental node keys will be in the first ⌈n/2⌉ positions of the array, while the leaf keys will occupy the last ⌊n/2⌋ positions.
• If you know the index (i) of any node you can find the parent, left child and right child index by following formula (assuming array index starts from 0).
  • Parent index = (i-1)/2;
  • Left child index = 2*i + 1;
  • Right child index = 2*i + 2;

Now it’s time to some real implementations of Heap data structure:

How can we construct a heap for a given array of keys? There are two waysfor doing this.

1. Bottom-up heap construction algorithm also known as MaxHeapify and trickleDown.
2. TopDown or trickleUp heap construction algorithm. This will be discussed in next section with priority queue.

MaxHeapify: You can think of MaxHeapify() as a simple method which convert an array to a heap. This algorithm works in bottom-up manner to convert an array A [0..n],where n is the size of Array, into a max-heap. It initializes the array as complete binary tree with n elements by placing elements in the order given and then it “Heapify” the tree as follows:

• • Starting with the last parental node (n/2th position), the algorithm checks whether the parent satisfy the heap condition or not i.e. parent node should be greater than its children.
  • If it does not, the algorithm exchanges the node’s key K with the larger key of its children and checks whether the heap condition holds for K in its new position.
  • This process continues until the heap condition for K is satisfied.
  • After completing the “heapification” of the subtree rooted at the current parental node, the algorithm proceeds to do the same for the node’s immediate predecessor. The algorithm stops after this is done for the root of the tree.

• • Let’s understand the algorithm with the help of above figure.

• • • • The last parental node is 10, we start from here. Compare this node with its largest children, in this case it is 12 therefore swap it with its largest child, now the 10 is at its position and there is no left and right child so we stop here.
      • Repeat same process for the second last parental node 8. This node satisfies the heap condition so do nothing here.
      • Repeat same process for the third last parental node 2. Compare this node with its largest children, in this case it is 12 therefore swap it with its largest child. Next check whether the node 2 satisfies the heap property at its new position, it’s not because left child 10 is greater than 2 so swap 2 with 10.
        Now the tree is a heap.

Java Code for Heap
Lets start with simple maxHeapify() method and subsequently we will add another method like heapSort() and PriorityQueue’s methods extractMax(), and insert().
To easily understand the code visualizes the Heap as an array.

package com.test.heap;

import java.util.Arrays;

public class Heap {

	private void maxHeapify(int[] heapArray, int index, int heapSize) {
		int largest = index;
		while (largest < heapSize / 2) { // check before leaf node only
			int left = (2 * index) + 1;//left child
			int right = left + 1;      //right child
			if (left < heapSize && heapArray[left] > heapArray[index]) {
				largest = left; 			}
			if (right < heapSize && heapArray[right] > heapArray[largest]) {
				largest = right;
			}
			if (largest != index) { // swap parent with largest child
				int temp = heapArray[index];
				heapArray[index] = heapArray[largest];
				heapArray[largest] = temp;
				index = largest;
			} else {
				break; // heap condition satisfied for index
			}

		}
	}

	public void builMaxHeap(int[] heapArray, int heapSize) {
		// we are not starting from 0 because we are swapping largest child to
		// the parent(see algorithm)
		for (int i = (heapSize - 1) / 2; i >= 0; i--) {
			maxHeapify(heapArray, i, heapSize);
		}
	}
	
	public static void main(String[] args) {
		int[] heapArray = { 1, 8, 9, 2, 10, 14, 3, 4, 7, 16 };
		
		System.out.println("Before heapify: "+Arrays.toString(heapArray));		
		new Heap().builMaxHeap(heapArray, heapArray.length);
		System.out.println("After heapify: "+Arrays.toString(heapArray));
		
	}
}

Output
--------
Before heapify: [1, 8, 9, 2, 10, 14, 3, 4, 7, 16]
After heapify : [16, 10, 14, 7, 8, 9, 3, 4, 2, 1]

Efficiency of maxHeapify()
As we have seen that Heap is a binary tree with some special property. A Heap tree height with N nodes is equal to ⌊log2^N⌋ or ⌈log2^{(N + 1)}⌉ − 1.
Let’s understand this once again-
Consider below Heap, here you can see the no of nodes N is 7 and height is 2. Let’s derive height through N. Remember log2^N means how many times you will raise 2 to get N. For ex. log2⁸=3 => 2³=8.
Height = ⌊log2^N⌋ => ⌊log2⁷⌋=2
Or Height = ⌈log2^N+1⌉-1 => ⌈log2⁷⁺¹⌉-1 =>⌈log2⁸⌉-1=> 3-1 = 2

We can observe that in worst case of the buildMaxHeap() algorithm each node value on level i of the tree will travel to the leaf level h. We requires two comparisons before moving node value to the next level down —one to find the larger child and the other to determine whether the exchange is required—the total number of key comparisons involving a key on level i will be 2(h − i). Confused! let’s clear the confusion with below example:

Here you can see that node 10 is at the level 1 (i=1) is violating the heap property and to determine whether this node is violating the heap property we need two comparisons- first to larger child which is 12 – second to compare whether the larger child is greater that its parent or not and hence there are 2 comparison at level i=1. We can see that 2(h-i) => 2(2-1)=2;
Therefore, the total number of key comparisons in the worst case will be directly proportional to the tree height(h). We can say that the running time of maxHeapify() on a node of height h as O(h) or O(log2^N).

What about the running time of buildMaxHeap()? It’s easy to compute the upper bound of buildMaxHeap()- we know that we are calling maxHeapify() in loop from 0 to N/2. Each call to maxHeapify() takes O(logn) time, and buildMaxHeap() makes O(n) such calls. Thus, the running time is O(nlogn).
Although above upper bound is correct but there is a tighter bound by which you can derive the running time cost to O(n). Let’s go deeper into this:

When mxHeapify() is called, the running time depends on how far an element might move down in tree before the loop terminates or we can say that it depends on the height of node. In the worst case the node value will move up to the leaf level.
Let’s see the work done at each level.
At the last row of the tree there are 2^h nodes – no call to maxHeapify .
At the second last row there are 2^{(h − 1)} node – and each might move down by 1 level.
At the third last row there are 2^{(h − 2)} nodes, and each might move down by 2 levels.
…
…
At the top row there are 2^{(h − h)} = 2⁰=1 nodes, and the node might move down up to the leaf i.e. equal to the height logn.
Here we can see that the nodes at the top may have to move maximum, but there are far fewer nodes near the top of the tree than the bottom. We can say that not all mxHeapify() operations are O(logn), this is why you are getting O(n).
↠↠Next ↠Heap Sort

Go to the next page – Click on the below red circle with page number.