-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeapSort.lua
More file actions
64 lines (54 loc) · 1.41 KB
/
Copy pathHeapSort.lua
File metadata and controls
64 lines (54 loc) · 1.41 KB
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
local heap = {}
function heap:init(func)
self.data = {};
self.sortedFunc = func
end
function heap:update(index)
local parent = math.floor(index / 2)
while(parent > 0 and self.sortedFunc(self.data[index], self.data[parent])) do
swap(self.data, index, parent);
index = parent;
parent = math.floor(index / 2);
end
end
function heap:insert(value)
table.insert(self.data, value)
self:update(#self.data);
end
function heap:pop()
local value = self.data[1]
self.data[1] = table.remove(self.data, #self.data)
local index = 1;
local cnt = #self.data
while(true) do
local value = self.data[index]
local newIndex = index;
local left = index * 2
if(left <= cnt) then
if(self.sortedFunc(self.data[left], self.data[newIndex])) then
newIndex = left
end
local right = left + 1
if(right <= cnt and self.sortedFunc(self.data[right], self.data[newIndex])) then
newIndex = right
end
end
if(newIndex ~= index) then
swap(self.data, newIndex, index)
index = newIndex
else
break;
end
end
return value
end
function sort(arr, func)
heap:init(func)
for i,v in ipairs(arr) do
heap:insert(v)
end
for i=1, #arr do
arr[i] = heap:pop();
end
end
return sort