Question about binary tree & heaps
 

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.
http://www.apcx.3rror.com/images/binaryTreeQuestion.JPG
...and determine when the equality is true.

Re: Question about binary tree & heaps
 

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.

Re: Question about binary tree & heaps
 

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.

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


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?

Re: Question about binary tree & heaps
 

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.

Re: Question about binary tree & heaps
 

AOA
i am sending u a link this is a very useful link. Because i am student of BSIT in Virtual University. i am sending your library link. if u have any problem it you can tell me.

http://www.vu.edu.pk/CourseOutline/cs301.html
http://vulms.vu.edu.pk/Links/CS301.htm

ok ALLAH HAFIZ.