Question

Assume that a max-heap with 10510^5105 elements is stored in a complete 5-ary tree. Approximately how many comparisons a call to Insert(){\tt Insert()}Insert() will make?

Answer 1

Answer:

K-ary heaps are a generalization of binary heap(K=2) in which each node have K children instead of 2. Just like binary heap, it follows two properties:

1) Nearly complete binary tree, with all levels having maximum number of nodes except the last, which is filled in left to right manner.

2) Like Binary Heap, it can be divided into two categories: (a) Max k-ary heap (key at root is greater than all descendants and same is recursively true for all nodes). (b) Min k-ary heap (key at root is lesser than all descendants and same is recursively true for all nodes)