Linked List

As we know that Array is very useful data structure but it has certain limitations:

1. changing the size of the array requires creating a new array and then copying all data from the array with the old size to the array with the new size and
2. the data in the array are next to each other sequentially in memory, which means that inserting or deleting an item inside the array requires shifting some other data in this array.

This limitation can be overcome by using linked structures. Linked lists is a simple data structure which contains individual elements(say nodes) with links between them and the nodes are arranged in a linear order. Each node in a linked list contains a reference (or link) to the next node. As compared to Array, Linked List has some advantage- Linked list is unbounded, deletion of an element is faster because only you have to change some links, there is no shifting of elements. You can use a linked list in many cases in which you use an array, unless you need frequent random access to individual items using an index.

Types of Linked List

• • Singly Linked List: If a node has a link only to its successor in a Linked List, then the list is called a singly linked list. A node includes two data fields: info and next. The info field is used to store information, and this field is important to the application. The next field is used to link together nodes to form a linked list. Last node point to null.
    

Java implementation of Singly Linked List

Create a Node class first which will keep info and link to the next element.

public class Node {

	int info;
	Node next;

	public Node(int info) {
		this.info = info;
	}

	public void displayNode() {
		System.out.print("[" + info + "]->;");
	}
}

Create LinkList class which will hold nodes.

public class LinkList {

	private Node first;
	
	public LinkList() {
		first = null;
	}
        public Boolean isEmpty(){
                return first == null;
        }
	public void insertFirst(int info) {
		Node node = new Node(info);
		node.next = first;
		first = node;
	}

	public void insertLast(int info) {
		Node node = new Node(info);
		if (first == null) {
			first = node;
		} else {
			Node current = first;
			while (current.next != null) {
				current = current.next;
			}
			current.next = node;
		}
	}

	public boolean delete(int info) {
		assert isEmpty(): "Empty list";
		// if it is the first element then move first one element further
		if (first.info == info) {
			first = first.next;
			return true;
		} else {
			Node current = first;
			Node previous = first;
			while (current != null && current.info != info) {
				previous = current;
				current = current.next;
			}
			if (current != null) {
				previous.next = current.next;
				return true;
			} else {
				System.err.println("No match found in the list for value:"+ info);
				return false;
			}
		}
	}

	public Node find(int info) {
		assert isEmpty(): "Empty list";
		Node current = first;
		while (current != null && current.info != info) {
			current = current.next;
		}
		if (current != null) {
			return current;
		} else {
			System.err.println("No match found in the list for value:" + info);
			return null;
		}
	}

	public void displayList() {
		Node current = first;
		while (current != null) {
			current.displayNode();
			current = current.next;
		}
		System.out.println();
	}

	public static void main(String[] args) {
		LinkList linkedList1 = new LinkList();
		linkedList1.insertFirst(5);
		linkedList1.insertFirst(10);
		linkedList1.insertFirst(15);
		linkedList1.insertFirst(20);
		System.out.println("First List-");
		linkedList1.displayList();
		linkedList1.delete(15);
		System.out.println("After deleting 15-");
		linkedList1.displayList();

		LinkList linkedList2 = new LinkList();
		linkedList2.insertLast(5);
		linkedList2.insertLast(10);
		linkedList2.insertLast(15);
		linkedList2.insertLast(20);
		System.out.println("Second List-");
		linkedList2.displayList();
		linkedList2.delete(5);
		System.out.println("After deleting first element 5-");
		linkedList2.displayList();

	}
}
Output
-------
First List-
[20]->[15]->[10]->[5]->
After deleting 15-
[20]->[10]->[5]->
Second List-
[5]->[10]->[15]->[20]->
After deleting first element 5-
[10]->[15]->[20]->

Let’s understand each methods in detail.
insertFirst(): This method insert a new node at the beginning of the list. This is very simple – create a new Node to insert and points its next to the old first, now you have new Node at the start so make it first. Using insert first you can create a Stack. It take O(1) time.

insertLast(): This method insert a new node at the end of the list. You traverse the whole list to reach at the last position. Point the next pointer of last to the new Node. It takes O(n) time where n is the current size of the list.

delete(): Delete the Node of given value. If the first Node contain the value then just move first to the next element of first else traverse the list to find the Node, maintain current and previous pointer where previous will point to the previous Node of current. After finding node just point previous->next to current->next. In worst case it will take O(n) time where the element is at the last position or there is no such element in list.

find(): This method traverse the list and match each Node value to the given value, if match is found it return the Node. In worst case it will take O(n) time where the element is at the last position or there is no such element in list.

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

Google Custom Search Programmatically

Using JSON/Atom Custom Search API, you can use RESTful requests to get either web search or image search results in JSON or Atom format.

Pricing options for Google Custom Search
JSON/Atom Custom Search API pricing and quotas depend on the engine’s edition:

1. Custom Search Engine (free): For CSE users, the API provides 100 search queries per day for free. If you need more, you may sign up for billing in the Cloud Console. Additional requests cost $5 per 1000 queries, up to 10k queries per day.
2. Google Site Search (paid): For detailed information on GSS usage limits and quotas, please check GSS pricing options.

Prerequisites for Google Custom Search
For performing google search through a program, you will need a developer api key and a custom search engine id.

How to get Google Developers API key?
Step 1: Log in to Google Developers Console with your google id (gmail).
Step 2: Create a project. Click on create project.

Step 3: Enter Project Name. Check the agreement check box and click on create.

Step 4: Now you can see the Project dashboard of newly created project. Now click on APIs & auth ->auth. Switch on the Custom Search API, by default it is off.

Step 5: Click on Credentials -> Create New Key (under Public api access)

Step 6: Click on Server key.

Step 7: Save your API key in notepad.

How to create Google Custom Search Engine?
Google Custom Search by Google allows web developers to include google search box in their web pages. The search box can be configured to search their own website or any other website they are configured to search.
Step 1: Log in to Google Custom Search
Step 2: Select New Search Engine
Step 3: Now you can enter the websites to be searched using google custom search. You can also include entire domains instead of specific websites as shown below.

Step 4: Click on create. It will show you below Screen.

Step 5: Click on get Code, note down the code (cx=xxxxx). If you want Google search box in you blog or website, you can copy paste the below script directly to your website.

Step 6: Your URL will look like below with search string “BasicsBehind”

Google Search Programmatically using JAVA

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.net.HttpURLConnection;
import java.net.URL;

public class CustomGoogleSearch {
	final static String apiKey = "AIzaSyAFmFdHiFK783aSsdbq3lWQDL7uOSbnD-QnCnGbY";
	final static String customSearchEngineKey = "00070362344324199532843:wkrTYvnft8ma";
	final static String searchURL = "https://www.googleapis.com/customsearch/v1?";

	public static String search(String pUrl) {
		try {
			URL url = new URL(pUrl);
			HttpURLConnection connection = (HttpURLConnection) url.openConnection();
			BufferedReader br = new BufferedReader(new InputStreamReader(connection.getInputStream()));

			String line;
			StringBuffer buffer = new StringBuffer();
			while ((line = br.readLine()) != null) {
				buffer.append(line);
			}
			return buffer.toString();
		} catch (Exception e) {
			e.printStackTrace();
		}
		return null;
	}
	private static String buildSearchString(String searchString, int start, int numOfResults) {
		String toSearch = searchURL + "key=" + apiKey + "&cx=" + customSearchEngineKey + "&q=";

		// replace spaces in the search query with +
		String newSearchString = searchString.replace(" ", "%20");

		toSearch += newSearchString;

		// specify response format as json
		toSearch += "&alt=json";

		// specify starting result number
		toSearch += "&start=" + start;

		// specify the number of results you need from the starting position
		toSearch += "&num=" + numOfResults;

		System.out.println("Seacrh URL: " + toSearch);
		return toSearch;
	}


	public static void main(String[] args) throws Exception {

		String url = buildSearchString("BasicsBehind", 1, 10);
		String result = search(url);
		System.out.println(result);

	}
}

You can add other parameters to Google search with ‘&’ operator, for example lr=lang_en restricts the search to documents written in a English language.
You can find complete list of parameters here:-
Parameters to pass with the search query to filter the results:
https://developers.google.com/custom-search/json-api/v1/reference/cse/list#response
Language and country codes to pass with query:
https://developers.google.com/custom-search/docs/xml_results#countryCodes

I would highly recommend to read below posts before getting into questions on stack and queue-

• Stack Data Structure
• Queue Data Structure

Questions On Stack and Queue

Problem-1: Show how to implement a queue using two stacks.

The difference between stack and queue is the order, stack uses last in first out(LIFO) and queue uses first in first out(FIFO). Our goal here is to convert LIFO to FIFO. To achieve FIFO using Stack somehow we will have to reverse the order of Stack. We can use our second Stack to reverse the order of the elements by popping from Stack-1 and pushing the elements on to Stack-2.

Stack-1 will thus be ordered with the newest elements on the top, while Stack-2 will have the oldest elements on the top. We push the new elements onto Stack-1, and peek and pop from Stack-2. When Stack-2 is empty, we’ll transfer all the elements from Stack-1 onto Stack-2, in reverse order.

public class QueueWithTwoStacks {
	Stack  oldStack;
	Stack  newStack;

	public QueueWithTwoStacks() {
		oldStack = new Stack();
		newStack = new Stack();
	}

	public int size() {
		return oldStack.size() + newStack.size();
	}

	public void enqueue(int value) {
		newStack.push(value);
	}

	public int dequeue() {
		shiftStack();
		return oldStack.pop();
	}

	private void shiftStack() {
		//shift only if old stack is empty
		if (oldStack.size() == 0) {
			while (newStack.size() > 0) {
				oldStack.push(newStack.pop());
			}
		}
	}
	
	public static void main(String[] args) {
		QueueWithTwoStacks queue = new QueueWithTwoStacks();
		queue.enqueue(10);
		queue.enqueue(18);
		queue.enqueue(5);
		queue.enqueue(29);
		queue.enqueue(27);
		queue.enqueue(6);
		
		System.out.println(queue.dequeue());
		System.out.println(queue.dequeue());
	}
}
Output
--------
10
18

Problem-2: Show how to implement a Stack using two Queues.

This is just opposite of above question. Here we have to convert FIFO to LIFO and using two Queues. The solution is very simple.

When Push() is called, enqueue() into Q1.

When Pop() is called, move up to Q1.size-1 elements from Q1 to Q2. Now Q1 has the last element, dequeue() this last element and move elements back from Q2 to Q1.

public class StackWithTwoQueues {

	Queue oldQueue;
	Queue newQueue;
	
	public StackWithTwoQueues(){
		oldQueue = new Queue();
		newQueue = new Queue();
	}
	
	public void push(int item){
		oldQueue.enqueue(item);
	}
	public Integer pop(){
		copy(oldQueue,newQueue,1);//leave last element in old queue
		int value =oldQueue.dequeue();//remove last element
		copy(newQueue,oldQueue,0);//copy back all the elements
		return value;
	}
	private void copy(Queue src,Queue target, int upto){
		if(target.size()==0){ 
			while(src.size()>upto){
				target.enqueue(src.dequeue());
			}
		}
	}
	
	public static void main(String[] args) {
		StackWithTwoQueues stack = new StackWithTwoQueues();
		stack.push(50);
		stack.push(10);
		stack.push(4);
		stack.push(34);
		stack.push(3);
		stack.push(12);
		stack.push(60);
		
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		
		
		stack.push(55);
		stack.push(33);
		
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
	}
	
}

Output
---------
60
12
3
33
55
34

Problem-3: Design a stack which, in addition to push() and pop(), also has functions min() which returns minimum element and max() which return maximum element. All operations should operate in O(1) time.

Here we will decorate the original Stack by extending from it. The MinMaxStack will have two Stacks to maintain minimum and maximum values.

public class MinMaxStack extends Stack{

	private Stack minStack;
	private Stack maxStack;
	
	public MinMaxStack(){
		minStack = new Stack();
		maxStack = new Stack();
	}
	
	public void push(int value){
		if(min() ==-1 || value < min()){
			minStack.push(value);
		}
		if(max() ==-1 || value > max()){
			maxStack.push(value);
		}
		super.push(value);
	}
	
	public int pop(){
		int value = super.pop();
		if(value == min()){
			minStack.pop();
		}
		if (value == max()) {
			maxStack.pop();
		}
		return value;
	}

	public int min() {
		if(minStack.size()>0){
			return minStack.peek();
		}
		return -1;
	}
	
	public int max() {
		if (maxStack.size() > 0) {
			return maxStack.peek();
		}
		return -1;
	}
	public static void main(String[] args) {
		MinMaxStack stack = new MinMaxStack();
		stack.push(50);
		stack.push(10);
		stack.push(4);
		stack.push(34);
		stack.push(3);
		stack.push(12);
		stack.push(1);
		System.out.println("MIN: "+stack.min());
		System.out.println("MAX: "+stack.max());
	}

}
Output
--------
MIN: 1
MAX: 50

Problem-4: Write a program to sort a stack in ascending order(with biggest item on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure.

We have two stacks. Suppose that S2 is sorted and S1 is not sorted.

When we pop 7 from S1, it should be placed at the right position in S2 ie just above 6. We already have two elements 8 and 12 above 6. We can place 7 at right position in S2 by popping 7 from S1 and keeping it in a temporary variable. Then moving all the items from S2 to S1 which is greater than 7 and then push 7 to S2. Repeat the process for all the items in S1.

public class SortedStack {

	public static Stack sortStack(Stack src){
		Stack r = new Stack();
		while(!src.isEmpty()){
			int temp = src.pop();
			while(!r.isEmpty() && r.peek() > temp){
				src.push(r.pop());
			}
			r.push(temp);
		}
		return r;
	}
	
	public static void main(String[] args) {
		Stack s = new Stack();
		s.push(10);
		s.push(12);
		s.push(8);
		s.push(7);
		s.push(11);
		s.push(5);
		Stack r =SortedStack.sortStack(s);
		for(int i=0;i<6;i++){
			System.out.print(r.pop()+" ");
		}
	}
}
Output
----------
12 11 10 8 7 5 

References:

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

↞↞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 ↠↠