Help with heap sort

[DanielG]

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

[Saad]

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.

[DanielG]

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.

[DanielG]

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?