Timeline for Partially sorted Max Heap
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2023 at 14:46 | comment | added | Russel | I am currently looking at it but you might be right. And your idea might work but how are you going to maintain that after this, the result is a max heap? Maybe perform an extra max heapify at the end? Again I am not quite sure yet. But thanks for pointing out the flaw. | |
| Feb 28, 2023 at 14:22 | comment | added | Avi Tal | Hi, appearently I found a counter example... If the leftmost path of the heap includes very large numbers, and the rest are smaller than all of the numbers on the leftmost path, this will not work. I came across a correct algorithm: Ignore the fact that it is a heap, reverse pardition around the median, and repeat this log(n) times for the left halves of the array... | |
| Jan 28, 2023 at 16:33 | vote | accept | Avi Tal | ||
| Jan 28, 2023 at 16:30 | comment | added | Russel | Actually you can skip $d =0$ since $H_0$ is already partially sorted, but if you do, then your example is correct. I started the algorithm with 0 to make the analysis more direct. | |
| Jan 28, 2023 at 16:27 | history | edited | Russel | CC BY-SA 4.0 |
added 1 character in body
|
| Jan 28, 2023 at 16:27 | comment | added | Avi Tal | Thanks!. It's starting to make sense! So you mean the process shoud not be stopped until the whole heap is "sorted", right? Otherwise for d=0... {100,20,50,...} can become {100,50,20...}. Am I correct? | |
| Jan 28, 2023 at 16:11 | comment | added | Russel | I made a small update in the algorithm. Let me use your example to show how it works. For $d=1$, we have $H_1= [20,50,10,11,30,40] $, because it should include everything from index $2^1=2$ to $2^3-1=7$. Now $j = 3$,so you need to find the element in $H_1$ that will be on index 3 when $H_d$ is reversed sorted, and that will 40. Partitioning around 40 will result to $[50,40,10,11,30,20]$ | |
| Jan 28, 2023 at 16:04 | comment | added | Avi Tal | Sorry... fixed my comment. So after d = 0, what do we get? Can we get {100,50,20,10,11,30,40}? Thanks | |
| Jan 28, 2023 at 16:01 | history | edited | Russel | CC BY-SA 4.0 |
added 9 characters in body
|
| Jan 28, 2023 at 16:01 | comment | added | Avi Tal | Thanks for the answer. A small issue: Take the array {100,20,50,10,11,30,40} which form a max-heap. When applying the partition around 20, which is the smallest at depth 1, 30 can replace it instead of 40. This seems to create a problem. Right? Or am I missing something? Thanks. – Avi Tal 14 mins ago Delete | |
| Jan 28, 2023 at 8:11 | history | edited | Russel | CC BY-SA 4.0 |
added 80 characters in body
|
| Jan 28, 2023 at 8:04 | history | edited | Russel | CC BY-SA 4.0 |
added 80 characters in body
|
| Jan 28, 2023 at 7:55 | history | answered | Russel | CC BY-SA 4.0 |