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 predefined size. Also study the relative efficiencies 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 file "IN" stands for insert and "EX" stand for extract-min operation.

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.