In class we studied binary heaps, i.e., heaps that store the elements in complet

Question

In class we studied binary heaps, i.e., heaps that store the elements in complete binary trees. This question is about ternary heaps, i.e., heaps that store the elements in complete ternary trees (where each node has at most three children, every level is full except for the bottom level, and all the nodes at the bottom level are as far to the left as possible). Here we focus on MAX heaps, where the priority of each node in the ternary tree is greater or equal to the priority of its children (if any) a. Explain how to implement a ternary heap as an array A with an associated Heapsize variable (assume that the first index of the array A is 1). Specifically, explain how to map each element of the tree into the array, and how to go from a node to its parent and to each of its children (if any) b. Suppose that the heap contains n elements. (1) What elements of array A represent internal nodes of the tree? Justify your answer. (2) What is the height of the tree? Justify your answer Consider the following operations on a ternary heap represented as an arrayA c. INSERT(A, key): Insert key into A . EXTRACT_MAX(A): Remove a key with highest priority from A .UPDATE A, i, key), where 1 s i s A.Heapsize: Change the priority of Al1] to key and restore the heap ordering property. REMoVE(A, i), where 1

Explanation / Answer

TERNARY HEAP:

HEIGHT:

Explaination.

every level has 3h nodes in ternary tree where h is the height of the tree and we have total nuber of node are n

so 3h = n

taking log we get h = log3n.

NO. OF LEAF NODES:

OPERATIONS:

These are the heap operations.

1. Insert

2. Find min

3. Delete min.

We can simulate these operations in BST. Below is the description of each of them.

Insert: BST has it's own insert function like Heap. But the disadvantage is, in the worst case, it may take O(n) time unlike O(logn) in Heap.

Find min: In Heap, we can find the min in O(1) time. In BST, the leftmost node contains the minimum number. So, starting from the root, we will need O(h) time to find the min where in the worst case h = n and in the best case h = logn. However, there is a better way to find the min in BST. We can keep an extra pointer which will always point to the leftmost node of BST. This pointer will be updated when an insert or delete is made. By this way, we can simulate find min in O(1) time.

Delete min: In Heap, Delete min takes O(logn) time in the worst case. Unlike that, in BST, it will take O(1) time to find the min and O(h) time[in worst case, h = n; best case, h = logn] to change the structure of the tree.

We can apply Delete Max operation k times in a Max_Heap to get the top-k-largest elements.

It will take O(klogn) time. However, using a second heap, we can do this in a faster way. Here goes the description. Copy the root of the given Max_Heap [lets call it X] and insert it into a new Max_Heap [lets call it Y, this is empty at the beginning].

Apply Delete Max in Y. This will give the first max element. Copy the first max element's children from X and insert into Y. Apply Delete Max in Y.

This will give the second max element. Copy the second max element's children from X and insert into Y. Apply Delete Max in Y. This will give the third max element. Do this K times. Each time, we are inserting two element from X into Y and deleting one element from Y.

So, the maximum number of elements in Y is (k+1). So, the height of Y will be logk. As, we are doing 2k number of insertion and k number of deletion, the order should be O(klogk).

BST is implemented using array data structure. We can apply Build_Heap on that array and get the Heap in O(n) time. If it was not implemented using array, we can traverse the BST in O(n) time and get it into an array.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.