We can represent complete binary trees sequentially within an array by simply putting the root at position 1, its children at positions 2 and 3, the nodes at the next level in positions 4, 5, 6, and 7, etc. The example is given below.

Example

This array representation is useful because it is very easy to get from a node to its parent and children. The parent of the node in position j is in position j/2 (rounded down to the nearest integer if j is odd), and conversely, the two children of the node in position j are in positions 2j and 2j+1. This makes traversal of such a tree even easier than if the tree were implemented with a standard linked representation (with each element containing a pointer to its parent and children).

A (binary) heap data structure is an array object that can be viewed as a complete binary tree. Each node of the tree corresponds to an element of the array that stores the value in the node. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point.

A heap is a complete binary tree, represented as an array, in which every node satisfies the heap condition or heap property. The heap property is that for every node i other than the root, the value of a node is at most the value of its parent, and the subtrees rooted at a node contain smaller values than does the node itself. In this way, the largest value is always in the first position in the array.

To be able to build a heap, it is necessary first to implement the insert operation. Since this operation will increase the size of the heap by one, number of elements (num_elts) in the heap must be also incremented. Then the node (that contains new value) to be inserted is put into Array[num_elts]. Note that we always insert a new node at the end, but this insertion may violate the heap property. If the heap property is violated (the new node is greater than its parent), then the violation can be fixed by exchanging the new node with its parent. This may, in turn, cause a violation, and thus can be fixed in the same way. For example, if P is to be inserted in the heap above, it is first stored in Array[13] (since it is the 13th element) as the right child of M. Then, since it is greater than M, it is exchanged with M, and since it is greater than O, it is exchanged with O, and the process terminates since it is less than X. The heap shown below is the result.

The code for this method is not difficult. We give the pseudocode for the insertion.

helper (k){
	int v;
	v = Array[k];
	while (Array[k/2] <= v) {
	     Array[k] = Array[k/2];
	     k = k/2;
	}
	Array[k] = v;
}

insert (v) {
	num_elts = num_elts + 1;       
	Array[num_elts] = v;
	helper(num_elts);
}

Your job is to implement insert functionality in SmallTalk.

We provide the simple template for the Heap . Copy the template into your working directory.

Heap is a subclass of Object. It has two instance variables: items and num_elts. "items" will be a structure that keeps all elements in the heap. "num_elts" indicates number of elements in the heap.

Next, create a class called HeapOC which is a subclass of Heap .

You are going to implement insert: method for HeapOC. Create a method init

  
init
	num_elts := 0.
	items := OrderedCollection new.

num_elts
	^num_elts.



increment
	num_elts := num_elts + 1.

print_heap

	| num counter tempindex |
	num := self num_elts.	
	counter := 1.
	tempindex := 1.

	[tempindex <= num]
	    whileTrue:
		[ Transcript show: (items at: tempindex) printString, '   '.
		   (tempindex = ((2 raisedTo: counter) - 1))
		    ifTrue: [ Transcript cr; cr.
			  counter := counter + 1].
						
	                      tempindex := tempindex + 1.].
	Transcript  cr; cr.

You have to implement insert method. And then you can test your insertion using the similar as below.

| temp |
temp := HeapOC new.
temp init.

temp insert: 'x'.
temp insert: 't'.
temp insert: 'o'.
temp insert: 'g'.
temp insert: 's'.
temp insert: 'm'.
temp insert: 'n'.
temp insert: 'a'.
temp insert: 'e'.
temp insert: 'r'.
temp insert: 'a'.
temp insert: 'i'.
temp print_heap.

The result should like

'x'

't'  'o'

'g'  's'  'm'  'n'

'a'  'e'  'r'  'a'  'i'

If you insert 4 more elements in the above code, i.e., 'p', 'y', 'z', and 'a' in this order, you should get the following heap

'z'   

't'   'y'   

'g'   's'   'o'   'x'   

'a'   'e'   'r'   'a'   'i'   'm'   'n'   'p'   

'a'   

Turning In...... Attention!!!!

All students must turn in their lab #4 to "tee@cc.gatech.edu"

Remember to quit your VisualWork before you close your window management system.

References: