4

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?

gsamaras
  • 71,951
  • 46
  • 188
  • 305
shubhvash
  • 61
  • 4
  • 1
    The more elements you extract this way the less you make use of the heap structure. So my guess is it will quickly get slower with increasing k. – Henry Sep 24 '17 at 09:35
  • yes i suspect that too. but i still want an algorithm to generalize it for k. – shubhvash Sep 24 '17 at 09:42
  • 1
    It will definitely hurt performance. It's *possible* that removing two elements in this way would not harm performance, but it wouldn't increase performance. Any more than two, though, and you'll be spending too much time trying to find the Kth largest element. @gsamaras provided a link to the algorithm for finding the Kth largest element. – Jim Mischel Sep 25 '17 at 00:43

1 Answers1

2

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

gsamaras
  • 71,951
  • 46
  • 188
  • 305