Heap sorting
sinsinac
help.docx1
Part I: written exercises.
1. Using the Red-Black Tree applet, you input the following numbers into the Red-Black tree, keep all red-black rules ( see the red-black rule on the bottom of the exercise ) either using color changes or rotation. The result graph should be height balance and red-black correct.
You need to follow the rules, randomly color change and rotation will result in zero credit even the result could be red-black correct.
Attach your results of screen shots for every question.
a. Insert 50, 70, 20, 90
b. Insert 50, 70, 20, 90, 99
c. Insert 50, 70, 20, 90, 80
d. Insert 50, 70, 20, 80, 60, 90, 75, 95
e. Insert 50, 70, 20, 90, 60, 55, 65, 68
Red-Black Rules
When inserting (or deleting) a new node, certain rules, which we call the red-black rules, must be followed. If they’re followed, the tree will be balanced. Let’s lookbriefly at these rules:
1. Every node is either red or black.
2. The root is always black.
3. If a node is red, its children must be black (although the converse isn’t necessarily true).
4. Every path from the root to a leaf, or to a null child, must contain the same
number of black nodes.
2. Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function h(x) = x %10 (table size is 10), showing the resulting
a. Separate chaining hash table
b. Open addressing hash table using linear probing.
c. Open addressing hash table using quadratic probing.
d. Open addressing hash table with second hash function h2(x) = 7- (x %7)
3. Draw the figures to show steps how to convert the binary tree to a heap using the Heapify algorithm.
( 4 5 2 6 7 3 1 )
4. Using the diagrams (see the attached example of heap sort) to trace the action of heapsort on the list of 1, 7, 2, 6, 3, 5, 4, give every state of your tree such as finishing a heapify or removing the root.
Part II: programming exercise
Implement the PriorityQ class in the priorityQ.java program (Listing 4.6) using
a heap instead of an array. You should be able to use the Heap class in the
heap.java program (Listing 12.1) without modification. Make it a descending
queue (largest item is removed).
Listing 4.6
The priorityQ.java Program
// priorityQ.java
// demonstrates priority queue
// to run this program: C>java PriorityQApp
////////////////////////////////////////////////////////////////
class PriorityQ
{
// array in sorted order, from max at 0 to min at size-1
private int maxSize;
private long[] queArray;
private int nItems;
//-------------------------------------------------------------
public PriorityQ(int s) // constructor
{
maxSize = s;
queArray = new long[maxSize];
nItems = 0;
}
//-------------------------------------------------------------
public void insert(long item) // insert item
{
int j;
if(nItems==0) // if no items,
queArray[nItems++] = item; // insert at 0
else // if items,
{
for(j=nItems-1; j>=0; j--) // start at end,
{
if( item > queArray[j] ) // if new item larger,
queArray[j+1] = queArray[j]; // shift upward
else // if smaller,
break; // done shifting
} // end for
queArray[j+1] = item; // insert it
nItems++;
} // end else (nItems > 0)
} // end insert()
//-------------------------------------------------------------
public long remove() // remove minimum item
{ return queArray[--nItems]; }
//-------------------------------------------------------------
public long peekMin() // peek at minimum item
{ return queArray[nItems-1]; }
//-------------------------------------------------------------
public boolean isEmpty() // true if queue is empty
{ return (nItems==0); }
//-------------------------------------------------------------
public boolean isFull() // true if queue is full
{ return (nItems == maxSize); }
//-------------------------------------------------------------
} // end class PriorityQ
////////////////////////////////////////////////////////////////
class PriorityQApp
{
public static void main(String[] args) throws IOException
{
PriorityQ thePQ = new PriorityQ(5);
thePQ.insert(30);
thePQ.insert(50);
thePQ.insert(10);
thePQ.insert(40);
thePQ.insert(20);
while( !thePQ.isEmpty() )
{
long item = thePQ.remove();
System.out.print(item + “ “); // 10, 20, 30, 40, 50
} // end while
System.out.println(“”);
} // end main()
//-------------------------------------------------------------
} // end class PriorityQApp
Listing 12.1
// heap.java
// demonstrates heaps
// to run this program: C>java HeapApp
import java.io.*;
////////////////////////////////////////////////////////////////
class Node
{
private int iData; // data item (key)
// -------------------------------------------------------------
public Node(int key) // constructor
{ iData = key; }
// -------------------------------------------------------------
public int getKey()
{ return iData; }
// -------------------------------------------------------------
public void setKey(int id)
{ iData = id; }
// -------------------------------------------------------------
} // end class Node
////////////////////////////////////////////////////////////////
class Heap
{
private Node[] heapArray;
private int maxSize; // size of array
private int currentSize; // number of nodes in array
// -------------------------------------------------------------
public Heap(int mx) // constructor
{
maxSize = mx;
currentSize = 0;
heapArray = new Node[maxSize]; // create array
}
// -------------------------------------------------------------
public boolean isEmpty()
{ return currentSize==0; }
// -------------------------------------------------------------
public boolean insert(int key)
{
if(currentSize==maxSize)
return false;
Node newNode = new Node(key);
heapArray[currentSize] = newNode;
trickleUp(currentSize++);
return true;
} // end insert()
// -------------------------------------------------------------
public void trickleUp(int index)
{
int parent = (index-1) / 2;
Node bottom = heapArray[index];
while( index > 0 &&
heapArray[parent].getKey() < bottom.getKey() )
{
heapArray[index] = heapArray[parent]; // move it down
index = parent;
parent = (parent-1) / 2;
} // end while
heapArray[index] = bottom;
} // end trickleUp()
// -------------------------------------------------------------
public Node remove() // delete item with max key
{ // (assumes non-empty list)
Node root = heapArray[0];
heapArray[0] = heapArray[--currentSize];
trickleDown(0);
return root;
} // end remove()
// -------------------------------------------------------------
public void trickleDown(int index)
{
int largerChild;
Node top = heapArray[index]; // save root
while(index < currentSize/2) // while node has at
{ // least one child,
int leftChild = 2*index+1;
int rightChild = leftChild+1;
// find larger child
if(rightChild < currentSize && // (rightChild exists?)
heapArray[leftChild].getKey() <
heapArray[rightChild].getKey())
largerChild = rightChild;
else
largerChild = leftChild;
// top >= largerChild?
if( top.getKey() >= heapArray[largerChild].getKey() )
break;
// shift child up
heapArray[index] = heapArray[largerChild];
index = largerChild; // go down
} // end while
heapArray[index] = top; // root to index
} // end trickleDown()
// -------------------------------------------------------------
public boolean change(int index, int newValue)
{
if(index<0 || index>=currentSize)
return false;
int oldValue = heapArray[index].getKey(); // remember old
heapArray[index].setKey(newValue); // change to new
if(oldValue < newValue) // if raised,
trickleUp(index); // trickle it up
else // if lowered,
trickleDown(index); // trickle it down
return true;
} // end change()
// -------------------------------------------------------------
public void displayHeap()
{
System.out.print(“heapArray: “); // array format
for(int m=0; m<currentSize; m++)
if(heapArray[m] != null)
System.out.print( heapArray[m].getKey() + “ “);
else
System.out.print( “-- “);
System.out.println();
// heap format
int nBlanks = 32;
int itemsPerRow = 1;
int column = 0;
int j = 0; // current item
String dots = “...............................”;
System.out.println(dots+dots); // dotted top line
while(currentSize > 0) // for each heap item
{
if(column == 0) // first item in row?
for(int k=0; k<nBlanks; k++) // preceding blanks
System.out.print(‘ ‘);
// display item
System.out.print(heapArray[j].getKey());
if(++j == currentSize) // done?
break;
if(++column==itemsPerRow) // end of row?
{
nBlanks /= 2; // half the blanks
itemsPerRow *= 2; // twice the items
column = 0; // start over on
System.out.println(); // new row
}
else // next item on row
for(int k=0; k<nBlanks*2-2; k++)
System.out.print(‘ ‘); // interim blanks
} // end for
System.out.println(“\n”+dots+dots); // dotted bottom line
} // end displayHeap()
// -------------------------------------------------------------
} // end class Heap
////////////////////////////////////////////////////////////////
class HeapApp
{
public static void main(String[] args) throws IOException
{
int value, value2;
Heap theHeap = new Heap(31); // make a Heap; max size 31
boolean success;
theHeap.insert(70); // insert 10 items
theHeap.insert(40);
theHeap.insert(50);
theHeap.insert(20);
theHeap.insert(60);
theHeap.insert(100);
theHeap.insert(80);
theHeap.insert(30);
theHeap.insert(10);
theHeap.insert(90);
while(true) // until [Ctrl]-[C]
{
System.out.print(“Enter first letter of “);
System.out.print(“show, insert, remove, change: “);
int choice = getChar();
switch(choice)
{
case ‘s’: // show
theHeap.displayHeap();
break;
case ‘i’: // insert
System.out.print(“Enter value to insert: “);
value = getInt();
success = theHeap.insert(value);
if( !success )
System.out.println(“Can’t insert; heap full”);
break;
case ‘r’: // remove
if( !theHeap.isEmpty() )
theHeap.remove();
else
System.out.println(“Can’t remove; heap empty”);
break;
case ‘c’: // change
System.out.print(“Enter current index of item: “);
value = getInt();
System.out.print(“Enter new key: “);
value2 = getInt();
success = theHeap.change(value, value2);
if( !success )
System.out.println(“Invalid index”);
break;
default:
System.out.println(“Invalid entry\n”);
} // end switch
} // end while
} // end main()
//-------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//-------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
//-------------------------------------------------------------
} // end class HeapApp
