Consider the heap-as-array ADT given in lectures:
typedef struct HeapRep { Item *items; // array of Items int nitems; // #items in array int nslots; // #elements in array } HeapRep; typedef HeapRep *Heap;
If a heap is created to hold up to 10 Items, and Items are integer values, and higher values have higher priority, show the state of the heap after each of the following operations:
Heap h; Item it; h = newHeap(10); insert(h, 10); insert(h, 5); insert(h, 15); insert(h, 3); insert(h, 16); insert(h, 13); insert(h, 6); it = delete(h); insert(h, 2); it = delete(h); it = delete(h); it = delete(h); it = delete(h); it = delete(h);
Answer:
The following shows each operation and then the state of the heap after that operation. Note that since nslots remains as 10 for the entire lifetime of the Heap, we don't show it
Operation nitems [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] h = newHeap(10); 0 - - - - - - - - - - insert(h, 10); 1 10 - - - - - - - - - insert(h, 5); 2 10 5 - - - - - - - - insert(h, 15); 3 15 5 10 - - - - - - - insert(h, 3); 4 15 5 10 3 - - - - - - insert(h, 16); 5 16 15 10 3 5 - - - - - insert(h, 13); 6 16 15 13 3 5 10 - - - - insert(h, 6); 7 16 15 13 3 5 10 6 - - - it = delete(h); 6 15 6 13 3 5 10 - - - - insert(h, 2); 7 15 6 13 3 5 10 2 - - - it = delete(h); 6 13 6 10 3 5 2 - - - - it = delete(h); 5 10 6 2 3 5 - - - - - it = delete(h); 4 6 5 2 3 - - - - - - it = delete(h); 3 5 3 2 - - - - - - - it = delete(h); 2 3 2 - - - - - - - -
Repeat the above sequence of insertions an deletions, but this time draw the heap as a binary tree, with the highest value at the root and the values decreasing as you move down any branch.
Answer:
It's much easier to consider the heap as a tree, e.g.
Derive a formula for the minimum height of a Binary Search Tree containing n nodes. You might find it useful to start by considering the characteristics of a tree which has minimum height. The following diagram may help:
Answer:
A minimum height tree must be balanced. In a balanced tree, the height of the two subtrees differs by at most one. In a perfectly balanced tree, all leaves are at the same level. The single-node tree, and the two trees on the right in the diagram above are perfectly balanced trees. Let us consider perectly balanced trees initially. A perfectly balanced tree of height h will contain 1 node on the first level, 2 nodes on the second level, 4 nodes on the third level, 8 nodes on the fourth level, and so on. The j th level in a perfectly balanced tree always contains 2 j-1 nodes.
The number of nodes in a perfectly balanced tree of height h = 20+21+22+...+2h-1 = 2h-1
And, by rearranging the formula, we have h = log2(n+1)
By inspection of the trees that are not perfectly-balanced above, it is clear that as soon as an extra node is added to a perfectly balanced tree, the height will increase by 1. To maintain this height, all subsequent nodes must be added at the same level. The height will thus remain constant until we reach a new perfectly balanced state.For a tree with n nodes, minimum h = ceil(log2(n+1))
Explain how we could globally balance a binary search tree using the partition function.
Answer:
We move the median node of a given tree to the root of the tree by partitioning on (size/2). By having the median element at the root of the tree, we will end up with approximately the same amount of keys in the left subtree and the right subtree. If we repeat this process for every subtree in the tree, we will have a balanced tree.10 / \ 9 11 / 8 / 7
11 / 7 \ 8 \ 9 \ 10
10 / \ 9 11 / 8 / 7