A k-ary heap is like a binary heap (where k = 2), but (with one possible excepti

Question

A k-ary heap is like a binary heap (where k = 2), but (with one possible exception) non-leaf nodes have k children instead of 2 children. Implement k-ary heap as a min-priority queue for an arbitrary k 2 to support following operations:  insert (x): inserts the element x to the heap.  extract-min(): removes and returns the element of heap with the smallest key. k-ary heap is to be implemented using an array of predened size. Also study the relative eciencies of the data structure for varying values of k, by measuring the time required for performing sequence of operations given the input file for k = 2, 4, 6, 8, 10. In the input le IN" stands for insert and EX" stand for extract-min operation. An AVL tree is a binary tree that is height balanced: for each node x, the heights of the left and right subtrees of x differ by at most 1. Implement an AVL tree to support following operations.  insert(x): inserts an element x to the tree.  min(): returns the element with the smallest key.  max(): returns the element with the largest key.  in order-traversal(): to traverse a non-empty binary tree in in order, perform the following operations recursively at each node: (1) traverse the left subtree. (2) Visit the root (print the key for the element at root). (3) traverse the right subtree  search(x): returns TRUE if a node containing element x is found in a binary tree else returns FALSE.  successor(x): returns successor of element x i.e. element with the smallest key greater than that of element x.  predecessor(x): returns predecessor of element x i.e. element with the largest key smaller than that of element x. Augment the AVL tree to support following order-statistics operations.  select(i): returns the element containing ith smallest key in a binary tree. 1  rank(x): returns the rank/position of element x in the liner order determined by inorder traversal of tree. Conduct the timing experiments for the sequence of operations listed in the given input files. Each line in the input file is one the following commands:  IN: insert  MI: min  MA: max  TR: inorder-traversal  SR: search  SC: successor  PR: predecessor  SE: select  RA: rank Compare performance of heap sort and merge sort for sorting an input array of length n. Each element in the input array is a random number in the range 1 to n. Conduct the timing experiment for n = 1k; 2k; 4k; :::; 128k. Note: 1. This programming homework is to be done in pairs (groups of 2 students). Either C, C++ or java can be used as a programming language. (If you choose C++ as a programming language, you can download file timer.h and timer.cpp, which are useful for timing experiments.) 2. For both the question, element x contains only key with no satellite information and keys can be assumed to be distinct. 3. Executing the program for a particular input file should generate output file containing result of each operation (except insert) line by line. Please look at the sample output file (contains comments after symbol n" which are only for understanding purpose and need not be part of actual output file). Last line in the output file should give time required to execute the complete sequence of operations with appropriate time unit. 4. Input files attached are sample input files only. Final input files to run your program against will be posted later.

Explanation / Answer

A binary heap is implemented as an almost full (=complete) binary tree. For your k-ary heap, you will probably need to generate almost full k-ary tree [all levels in the tree are full, except the last one, inwhich you fill the tree from left to right] , and repeat the same ops the original heap do, but with more then 2 children per node. With some knowledge on heap ops, especially the heapify, and the tip above, it shouldn't be too hard to implement your k-ary heap. To implement it as an array, simply follow how a binary tree is implemented as an array, and follow these ideas when you implement your complete k-ary tree as an array.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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