-
-
Notifications
You must be signed in to change notification settings - Fork 101
/
heap_sort.jl
69 lines (58 loc) · 2.67 KB
/
heap_sort.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
"""
idx_for(i::Int)
Simple helper function for converting 0-based indices to Julia's 1-based indices.
"""
function idx_for(i::Int)
return i + 1
end
"""
heap_sort!(arr::Vector{T}, gt = >, N::Int = length(arr)) where {T}
Sort the given vector (in-place) using the Heapsort algorithm.
Heapsort consists of two stages:
1. Building a (max) heap of the array
2. Repeatedly extracting the largest element and inserting it at the front of the sorted part of the array
After the largest element has been extracted, the tree is updated to maintain the heap property via a "sifting" operation.
Storing a heap in an array is pretty straightforward - for every node with index n, its children are stored at indices
2n + 1 and 2n + 2 (for 0-based indices). Index 0 contains the root node.
Since Julia's indices are 1-based, we need to change this a little bit. We're using a trivial helper function
idx_for to convert from 0-based to 1-based.
See https://en.wikipedia.org/wiki/Heapsort for a complete explanation of Heapsort.
Contributed By:- [Frank Schmitt](https://github.com/frankschmitt)
"""
function heap_sort!(arr::Vector{T}, gt = >, N::Int = length(arr)) where {T}
n = N
i = div(n, 2)
t = -1
while true
if i > 0 # First stage - Sorting the heap
i -= 1 # Save its index to i
t = arr[idx_for(i)] # Save parent value to t
else # Second stage - Extracting elements in-place
n -= 1 # Make the new heap smaller
if (n == 0)
return # When the heap is empty, we are done
end
t = arr[idx_for(n)] # Save last value (it will be overwritten)
arr[idx_for(n)] = arr[idx_for(0)] # Save largest value at the end of arr
end
parent = i # We will start pushing down t from parent
child = i * 2 + 1 # parent's left child
# Sift operation - pushing the value of t down the heap
while child < n
if (
child + 1 < n &&
gt(arr[idx_for(child + 1)], arr[idx_for(child)])
)
child += 1 # Choose the largest child
end
if (gt(arr[idx_for(child)], t)) # If any child is bigger than the parent
arr[idx_for(parent)] = arr[idx_for(child)] # Move the largest child up
parent = child # Move parent pointer to this child
child = parent * 2 + 1 # find the next child
else
break # t's place is found
end
end
arr[idx_for(parent)] = t
end
end