Modify the heapsort algorithm to extract k elements at a time from heap

user_4051238 0
Viewed 374

While performing heapsort, only one max element is extracted from heap and swapped with element at the end of heap and then considered to be out of heap. Then heap property is restored using heapify. This is done till heap size becomes zero.

Instead of one suppose I extract two max elements from heap without calling heapify again in between. The second max element will be either second or third element of max-heap. for the second max element I can swap it with second last element of heap. Followed by similar steps of heapsort.

For extracting 3 max elements at a time, the third max element could be at any position in either {second, sixth, seventh} or {third, fourth, fifth} depending upon the position of second max-element. Let's say I find third max element's position by searching linearly within respective bounds.

I want to generalize it for extracting k elements at a time from heap. Can you please give any useful insights?

heapsort binary-heap heap data-structures algorithm
1 Answers

This will harm performance severely and your heap will lose its performance!

The reason is that the more elements you extract at once, the more you ignore the heap's properties, since you need to search for the k-th larger element in its possible positions. As k increases, so will the the number of possible positions, and of course in a non linear relation.

Related: Kth largest element in a max-heap

user_24113200
Related