Page 1 of 1

Priority Queues- Arrays Rate Topic: ****- 1 Votes

#1 karabasf  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 202
  • View blog
  • Posts: 417
  • Joined: 29-August 10

Posted 21 April 2012 - 04:09 PM

Level: Beginner - Intermediate
Assumed knowledge: before you can start this tutorial, you are assumed to have knowledge of:

  • Arrays
  • The difference between primitive data types and Objects (e.g. difference between int and Integer)
  • Conditional statements
  • Loops (for and while loop constructions)
  • Basic Knowledge of Object Oriented Programming (mainly methods)


This tutorial will cover the implementation of a Sorted Array by means of (surprise!) an Array. Sorted Arrays can be used to to count sequence of numbers, retrieve the maximum values of an array and to sort data in either an ascending or a descending trend. Furthermore, the insertion method of a Sorted Array ensures that the array does not need to be sorted after an arbitrary element is inserted. Possible applications of a Sorted Array would be a Priority Queue or a ranked list (think of a high score list for example).
Although a linked list could be used for the implementation (which would then be a Sorted List instead), an array provides basic insight to implement the (insertion and removal) in a linked list. As this is not the scope of this tutorial, this assignment is left for the reader.

So before we start, we need to identify variables we need. First, we need a value to denote the capacity of the array. As we will be using an Object array (we're not using an array of primitive datatypes, this will become clear later in this tutorial), we will also need a variable denoting the size (amount of stored elements) in the array. Finally, we need an Object (for this example we'll be using the Integer object) to store the elements. So, to summarize, we need the following variables:

  • size, denotes the amount of stored items in the array
  • capacity, denotes the amount of items which can be stored in the array
  • Integer[] sortedArray, to actually store the elements in the array


Now the variables are identified, the operations of a Sorted Array. We should be able to add and to remove an item. Obviously, we need a string representation and a constructor which takes the capacity of the Sorted Array. So we can already identify two methods and one constructor. Next to these values, I'll use some helper methods to determine whether the Sorted Array is empty or full, and a method to double the capacity of the Sorted Array when it is full. So, in short, we can identify the following methods:

  • boolean isEmpty(), to determine if the Sorted Array is empty
  • boolean isFull(), to determine if the Sorted Array is full
  • void doubleCapacity(), to double the capacity of the array and to copy the original elements in the new array with twice the capacity
  • void add(int i), method to add an integer (note that I use a primitive data type here!) to the Sorted Array
  • Integer remove(int i), method to remove an integer at position i of the Sorted Array
  • int size(), a method to retrieve the amount of elements in the Sorted Array


So now all the methods and variables are defined, lets start with the constructor. The constructor should take the capacity as an argument and instantiate our Integer[] sortedArray with that size.
However, we want to prevent that the user enters a negative number or a number equal to 0. If we would instantiate the Sorted Array with a negative number, we would get a NegativeArraySizeException. This can be easily prevented by checking the input of capacity and if the capacity is smaller or equal to 0, we instantiate the sorted array with a standard capacity of lets say 10 (any value is possible). This check is fully optional, so you can omit it if you want.
Using this knowledge, our constructor looks like:

public class SortedArray{
	private Integer[] elements; 	//The Integer array to store the elements
	private int storedElements;		//An integer denoting the amount of stored elements of the Sorted Array
	private int capacity;			//An integer denoting the capacity of the Sorted Array
	
	//Default constructor, creates a sorted array with the capacity 10
	public SortedArray(){
		//Call the second constructor to create a Sorted Array with a capacity of 10
		this(10);		
	}
	
	//Overloaded constructor, creates a Sorted Array with an user specified capacity
	public SortedArray(int capacity){
		//Create the Sorted Array with the user capacity. If capacity is 0 or negative, construct a default Sorted Array
		if(capacity > 0){
			this.capacity = capacity;
			this.elements= new Integer[this.capacity];
		}
		else{
			this.capacity = 10;
			this.elements= new Integer[this.capacity];
		}
		
		this.storedElements = 0;
	}



Now, we can add the helper methods isEmpty(), isFull() and the method size(). Before we add these, we need to determine to determine when the Sorted Array is empty. This is only when the amount of storedElements is equal to 0. Same for when the list is full, this is when the amount of storedElements equals to the capacity of the Sorted Array. Thus, we can add:

//Determine if the SortedArray is full
public boolean isFull(){
	return (storedElements == capacity);
}

//Determine if the SortedArray is empty
public boolean isEmpty(){
	return (storedElements == 0);
}

//Retrieve the amount of stored elements in the Sorted Array
public int size(){
	return storedElements;
}



So now we defined our helper methods, lets define the doubleCapacity() method. We will be using the Arrays.copyof() method, which can be found in java.util, meaning that we have to import this package. Add import java.util.* in order to do so. So, as we want to double our capacity, this means that the variable capacity needs to become twice as big as it originally was. Thus:

//Double the capacity of the array and retain the original elements
private void doubleCapacity(){
	capacity = 2 * capacity; //Double the capacity
	this.elements= Arrays.copyOf(elements, capacity);
}



Note that it is not necessary to use a doubleCapacity() method, the implementation of it is optional for the functionining of the Sorted Array. Furthermore, I made this method private as I do not want to have users modifying the capacity of the Sorted Array manually; the Sorted Array should increase the capacity only when it is needed.

Now we get to the more interesting part, the add and remove algorithms. Lets consider the add algorithm first for a descending Sorted Array:

add(int newElement)
	//Create an integer object in order to insert it in our Integer[] elements array
	Integer newEntry = new Integer(newElement);

	//Double the capacity of the array when it is full
	if(sortedArray is full)
		doubleCapacity(); //Note that this is optional. We could also decide to throw an exception or just return the method after applying some logic

	//If the list is empty, we can add the element at first index
	if(sortedArray is empty){
		elements[0] = newEntry;
	}
	else{ //the element needs to be added elsewhere
		//We will start the add from the tail and shift elements
		int i= this.size();
		
		//Start looping from the end of the Sorted Array
		for(;(i>=1) && (elements[i-1].intValue() < newEntry.intValue()); i--)
			elements[i] = elements[i-1]; //Shift the lower elements to the right
		
		//Add the new entry at position i
		elements[i] = newEntry;
	}
	
	storedElements++;



Note that when one wants to achieve an ascending sorted array, the sign of the element value comparison can be swicthed, e.g "<" becomes ">"
So how does this look like? Well, consider we have the following Sorted Array and we want to add the number 8

[10][8][8][7][7][5][null] //Note that null elements can be present in our Integer array 



So, if we want to add 8, we have to move the elements 7, 7, 5 one step towards the right. Visualizing this:

#Iteration 1
i = 6
[10][8][8][7][7][5][5]

#Iteration 2
i = 5
[10][8][8][7][7][7][5]	

#Iteration 3
i = 4
[10][8][8][X][7][7][5]

//Stop iterations

//Add the new entry at X (the 4th element)	
[10][8][8][8][7][7][5]	//Our final result



Implementing our add method in Java results in:

//Method to add an element in the sorted array
public void add(int newElement){
	//Create an Integer object to insert the entry in the Sorted Array
	Integer newEntry = new Integer(newElement);
	
	//Check if the list is full. If so, double the capacity
	if(this.isFull())
		doubleCapacity();
	
	//Use our add algorithm
	//If the array is empty, the new element needs to be added at the first index
	if(this.isEmpty()){
		element[0] = newEntry;
	}
	else{
		//Get the amount of stored elements and loop from that element
		int i = this.size();
		
		//Loop till till the condition is met where the element should be added
		for(;((i >= 1) && (elements[i-1].intValue() > newElement)); i--)
			elements[i] = elements[i-1]; //Swap the elements
		
		//Add the element at position i
		elements[i] = newEntry;
	}
	
	//Increment the amount of stored elements
	storedElements++;
}



Now, one of our final methods will be the remove method. Consider this algorithm:

remove (int i)
	if(this.isEmpty() || (i < 0) || (i >= size))
		return null;	//If the index i is outside the regions where the elements are stored or the array is empty we can return null, as no element was removed (this was one of the reasons of why to use an object Integer rather than a primitive datatype). 
		
	//Store the temp element to return
	Integer deletedElement = elements[i];
	
	//Start removing the element and shift the subsequent elements to the "empty spot"
	for(; i < this.size() - 1 ; i++)
		elements[i] = elements[i+1];
	
	//Set the last element (located at size - 1) equal to null
	elements[this.size() - 1] = null;
	
	//Decrease the amount of stored elements
	storedElements--;
	
	//Return the removed Integer object
	return deletedElement;



So, lets visualize this again. Suppose we want to remove the first element (i = 0) from the following Sorted Array

[10][5][6][7][null]



Therefore, if we remove element [10] we need to shift all of our elements to the left. Furthermore, we need to make the direct element left of the null element equal to null. Visualizing this:

#Iteration 1
[5][5][6][7][null]

#Iteration 2
[5][6][6][7][null]

#Iteration 3
[5][6][7][7][null]

//Stop iterations
//Make the element at the position size-1 (remember that the original size was 4. Also, note that arrays are 0 based, so we need to set at index i = 3) is equal to null

[5][6][7][null][null]



Implementing this in Java:

public Integer remove(int i){
	//If the index i is outside the regions where the elements are stored or the array is empty we can return null, as no element is apparent to be removed
	if(this.isEmpty() || (i < 0) || (i >= size))
		return null;
		
	//Store the temp element to return
	Integer deletedElement = elements[i];
	
	//Start removing the element and shift the subsequent elements to the "empty spot"
	for(; i < this.size() - 1 ; i++)
		elements[i] = elements[i+1];
	
	//Set the last element at the position of size-1 equal to null
	elements[this.size()-1] = null;
	
	//Decrease the amount of stored elements
	storedElements--;
	
	//Return the removed Integer object
	return deletedElement;
}



Finally, we need a string representation of our SortedArray in Java. We know we need to loop from 0 till the amount of stored elements -1 (remember that arrays are zero based). A string representation of our SortedArray may look like:

//The string representation of the Sorted Array. Note that our string representation only shows the stored elements and not the full array
//Customizable
public String toString(){
	if(this.isEmpty())
		return "[ ]";
	else{
		String representation = "["
		
		//Append the string with entries
		for(int i = 0; i < this.size() ; i++)
			representation += elements[i] + ", ";
		
		//Trim away the last comma and return the string
		return representation.substring(0, representation.length() - 2) +"]";
	}
}



The final code should look like:
Spoiler


To summarize everything, we designed a Sorted Array. Although some of its operations are still limited, could be expanded or can be differently specified, the reader should now be able to easily expand or modify the functionality of the Sorted Array. Some ideas would be:

  • getIndex(int value), get the index of where an element is stored (Think smart, the array is sorted!
  • remove(int value), instead of removing an integer by passing the position, remove the integer based on the value
  • toArray(), make a method which transforms the Sorted Array from i = 0 till i = amount of stored elements to an array
  • countNr(int value), count the occurence of a arbitrary number


Furthermore, with the logic of the proposed algorithms, the reader should be able to design its own Sorted (Double) Linked List. Adding and removing elements however differs from an ordinary array. As this is not the scope of this tutorial, the excercise is left to the reader.

Finally, it should be noted that a sorted array of objects can only be implemented when the objects can be compared against eachother, e.g. there should be a definition for when an Object1 has a "larger value/is bigger" than Object2.

I hope this tutorial was helpful for you ^^

References:
Data Structures & Algorithms in Java by Michael T. Goodrich and Roberto Tamassia

Is This A Good Question/Topic? 2
  • +

Page 1 of 1