Member Avatar for apcxpc

Hi all

Here are two questions from my Algorithms & Complexity Theory assignment.


1. A complete binary tree is a binary tree in which every level, except possibly the deepest, is completely filled. At depth n, the height of the tree, all the nodes must be as far left as possible. The concept of a complete binary tree extends to the concept of a complete k-ary tree in an obvious way, k>=2.

a) Show how a complete k-ary tree can be implemented efficiently using an array.
b) Design and analyze a procedure for inserting an element into a k-ary heap implemented using an array
c) Design and analyze a procedure for deleting an element from a k-ary heap implemented using an array
d) Design and analyze a k-ary heapsort.


2.
[img]http://www.apcx.3rror.com/images/binaryTreeQuestion.JPG[/img]
...and determine when the equality is true.

  • 3 Contributors
  • 4 Replies
  • 257 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by ITgeneration
Member Avatar for apcxpc

Here is my answer to the first one.

a) 
struct heap{
         int maxsize;   //maximum size of the heap
         element[] table;  //array containing elements of the heap
         int last;   //array index of the last element
}
The root of the heap is always stored at array index 1. 
Then, for a given node at index i:
The parent of this node is stored at index: (i-2)/k + 1.  (...if i>1)
The j-th child of this node is stored at index: d(i-1) + j + 1.
Then every array index from 1 and last contains a heap element, and there is no wasted space in the array.


b)

int parent(i){
	return (i-2)/d + 1
}

int child(i, j){
	return k(i-1) + j + 1;
}

heap Insert(heap h, element x){
	i = h.last + 1;
	p = parent(i);
	while (i > 1) and (h.table[i] < h.table[p] do{
		swap(h.table[i], h.table[p]);
		i = p;
	}
	return h;
}



c)  

//this method returns array index of given element, starts search at given index of heap's array
int search (heap h, element x, int index){
	if (h.table[index]==x) return index;
	for (int m=1; m<=k; m++){  //iterating through each of this nodes k children
		c = child(index, m);
		if (c > last) return null;
		int address = search(x, c);
		if (address!=null) return address;  
	}
	return null;
}

int deleteElement(heap h, element x){
	int address = search(h, x, 1);
	if (address==null) return h;
	d = h.last-1;
	h.last=d;
	h.table[address] = h.table[d+1];
	i = address;
	c = child(i,1);
	while (c <= d){
		if (h.table[i] > h.table[c]) swap(h.table[i], h.table[c]);
		i = c;
		c = child(c,1);
	}
	return h;	
}



d)

list Heapsort(list L){
	h := emptyheap;
	for x from first to last element of L do
		h = insert(h,x);
	LL = emptylist;
	while not empty(h) do{
		LL = LL.root(h)
		h = delete(h, root(h));
	}
	return LL;
}

I'm not very sure of my solutions to c) and d).

Also, both the deleteElement and insert procedure will have running time O(heapHeight) or O(heapSize), which is the same for the case of a binary heap. (I think). So I dont understand why the running time of k-ary Heapsort would be any different to binary Heapsort.

Member Avatar for apcxpc

For the Binary Tree Question, I know that the equation is true, from having tried examples of it.

e.g. from the following sketch, the sum would be: 1/8 + 1/8 + 1/4 + 1/2 = 1.
And the equality is true whenever the binary tree is full/complete, i.e. each node has 0 or 2 children.

[img]http://www.apcx.3rror.com/images/binaryTreeSketch.JPG[/img]


But I don't know how to make a formal proof of this. Would greatly appreciate some help with this.
If I were to use induction, what would the base case, and n-th case be? Do I use an example of a complete/incomplete binary tree?

Member Avatar for Rashakil Fol

Your base case would be a tree of height zero (with one node); your nth case would be a tree of height n, and you'd use strong induction. You could prove equality for the special case of a full tree -- unfull trees can be made into full trees by adding nodes, proving the inequality.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.