Computer Science Canada Help with heap sort |
| Author: | DanielG [ Wed Feb 06, 2008 5:51 pm ] |
| Post subject: | Help with heap sort |
I made a heap sort , yet for some reason it doesn't work (it works for the most part, but some numbers just don't get sorted). Can someone check it and tell me what the problem is? Here is the code : var stream : int open : stream, "heap.txt", get var size : int get : stream, size size -= 1 var heap : array 0 .. size of int var s : int := size proc switch (x, y : int) var temp := heap (x) heap (x) := heap (y) heap (y) := temp end switch proc heapify (x : int) if x not= 0 then if heap (x) < heap (floor ((x - 1) div 2)) then switch (x, (x - 1) div 2) heapify ((x - 1) div 2) end if end if end heapify proc deheap (x : int) if 2 * x + 1 < s then if heap (2 * x + 1) < heap (2 * x + 2) then switch (x, 2 * x + 1) deheap (2 * x + 1) else switch (x, 2 * x + 2) deheap (2 * x + 2) end if else switch (x, s) end if end deheap for i : 0 .. s get : stream, heap (i) heapify (i) end for var sorted : array 0 .. s of int for i : 0 .. size sorted (i) := heap (0) heap (0) := maxint deheap (0) s -= 1 end for var stream2 : int open : stream2, "sorted.txt", put for i : 0 .. size put : stream2, sorted (i) end for close : stream close : stream2 |
|
| Author: | Saad [ Wed Feb 06, 2008 6:58 pm ] |
| Post subject: | RE:Help with heap sort |
When removing the top element of a binary heap, replace the root with the last element in the tree, Also while removing you only check if heap (2 * x + 1) < heap (2 * x + 2) then But what happens when the heap(x) is less then both its children? The switch should then not even occur. |
|
| Author: | DanielG [ Wed Feb 06, 2008 7:42 pm ] |
| Post subject: | Re: Help with heap sort |
heap (x) is supposed to be less then both its children (since its min heap), and due to the nature of the heap it should never be more, so there is no point in checking if heap (X) > both its children. I don't think that is the problem. |
|
| Author: | DanielG [ Wed Feb 06, 2008 8:03 pm ] |
| Post subject: | Re: Help with heap sort |
I found what caused the problem, but I don't know how or why, the problem was decreasing the size of the heap with s-=1, but for some reason that caused some numbers not to sort properly, can someone tell me why? |
|