0
$\begingroup$

i have an idea of enhancing the heapsort by finding the max and min simultaneously and then swapping the max into the last node, and then the min will be swapped into the second to the last node, and then they will be removed or pop. and then they will be sorted in the array, the max will be at the last element, and the min will be at the beginning element.

question:

  1. is this applicable?
  2. will this improve the heapsort?
  3. what are the steps or ways i must do in order to implement this?(java)
$\endgroup$
6
  • $\begingroup$ I remember finding min&max as an improvement to selection sort (the twist being not to spoil stability). What kind of heap do you envision to find the max and min simultaneously? $\endgroup$
    – greybeard
    Commented Dec 13, 2023 at 12:12
  • $\begingroup$ I am trying to propose an enhanced heapsort that would combine the min and max heapify. I got the concept of this from the Double Selection Sort which works by finding the min and max values in the array and placing the max into the last index and the min in the starting index. How do i apply this to the heapsort? For visualization, this is what i want to happen: Original Array Form: [9, 1, 15, 2, 10] 9 / \ 1 15 / \ 2 10 $\endgroup$
    – user166089
    Commented Dec 13, 2023 at 12:30
  • $\begingroup$ --continuation Heapsort with min-max combination: 15 / \ 1 9 / \ 2 10 15 / \ 2 9 / \ 1 10 in this part, the second to the last element within the binary tree assumes the role of the minimum, while the maximum value is preserved. Specifically, in our example, the second-to-last value of the binary tree is 1, representing the minimum, while the max heapify is performed for the value 15. 10 / \ 2 9 / \ 1 15 here, the 1 will be place in the starting index and the 15 will be place in the last index. [1, ,15] $\endgroup$
    – user166089
    Commented Dec 13, 2023 at 12:31
  • $\begingroup$ --continuation 10 / \ 2 9 9 / \ 2 10 here, the max heapify is performed, and min is stay put since the 2 is the lowest value and is already placed in the second to the last index. and then, they will be deleted from the tree and be sorted in the array. [1, 2, 10, 15] 9 since, 9 is the only one left, it will be then deleted and inserted in the array. [1, 2, 9, 10, 15] SORTED $\endgroup$
    – user166089
    Commented Dec 13, 2023 at 12:31
  • 3
    $\begingroup$ What do you mean by "improve"? No asymptotic improvement is possible: all comparison-based sorting algorithms (like the one you propose) require $\Omega(n \log n)$ time, and heapsort already runs in time $O(n \log n)$. $\endgroup$
    – Steven
    Commented Dec 13, 2023 at 15:08

1 Answer 1

1
$\begingroup$

It doesn't matter how you pop, either min first, max first, or alternating. It is still $O(\log n)$ for each pop.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.