优先队列PriorityQueue

  1 PriorityQueue = PriorityQueue or {}
  2 
  3 --[[
  4        1
  5      /   \
  6     2     3
  7    / \   / \
  8   4   5 6   7
  9  /
 10 8
 11 2的子节点: 2*2和2*2+1, 3的子节点3*2和3*2+1
 12 反过来: 5的父节点floor(5/2), 6的父节点floor(6/3)
 13 ]]
 14 
 15 function PriorityQueue.new(compFunc)
 16     local inst = {
 17         _cname = "lang.PriorityQueue",
 18     }
 19 
 20     local arr = {}
 21     local len = 0
 22 
 23     local function swap(index1, index2)
 24         local t = arr[index1]
 25         arr[index1] = arr[index2]
 26         arr[index2] = t
 27     end
 28 
 29     function inst:count()
 30         return len
 31     end
 32 
 33     function inst:clear()
 34         for i=1,len do
 35             arr[i] = nil
 36         end
 37         len = 0
 38     end
 39 
 40     function inst:push(v)
 41         len = len + 1
 42         arr[len] = v
 43         local temp = len
 44         while temp > 1 do
 45             local parent = math.floor(temp / 2)
 46             if compFunc(arr[temp], arr[parent]) then
 47                 print("push swap: ", a, ": ", temp, parent, " value: ", arr[temp], arr[parent])
 48                 swap(temp, parent)
 49                 temp = parent
 50             else
 51                 break
 52             end
 53         end
 54     end
 55 
 56     function inst:pop()
 57         if len <= 0 then return end
 58 
 59         local ret = arr[1]
 60         arr[1] = nil
 61         if len > 1 then
 62             swap(len, 1)
 63         end
 64         len = len - 1
 65 
 66         local temp = 1
 67         while true do
 68             local lChild = temp * 2
 69             if lChild > len then break end
 70 
 71             local rChild = lChild + 1
 72             if rChild > len then
 73                 if not compFunc(arr[temp], arr[lChild]) then
 74                     swap(temp, lChild)
 75                     temp = lChild
 76                 else
 77                     break
 78                 end
 79             else
 80                 local lValue = arr[lChild]
 81                 local rValue = arr[rChild]
 82                 if lValue > rValue then --和大的交换
 83                     if not compFunc(arr[temp], arr[lChild]) then
 84                         swap(temp, lChild)
 85                         temp = lChild
 86                     else
 87                         break
 88                     end
 89                 else
 90                     if not compFunc(arr[temp], arr[rChild]) then
 91                         swap(temp, rChild)
 92                         temp = rChild
 93                     else
 94                         break
 95                     end
 96                 end
 97             end
 98         end
 99         return ret
100     end
101 
102     function inst:peek()
103         if len <= 0 then return nil end
104         local v = arr[1]
105         return v
106     end
107 
108     function inst:copyTo(dst)
109         assert("table" == type(dst), "copyTo: dst not table or Stack")
110         if "lang.PriorityQueue" == dst._cname then
111             for i=1,len do
112                 dst:push(arr[i])
113             end
114         else
115             for i=1,len do
116                 table.insert(dst, arr[i])
117             end
118         end
119     end
120 
121     function inst:__tostring()
122         if len <= 0 then return "" end
123         local strTb = {}
124         local pq = PriorityQueue(compFunc)
125         self:copyTo(pq)
126         while pq:count() > 0 do
127             table.insert(strTb, pq:pop())
128         end
129         return table.concat(strTb, ",")
130     end
131 
132     function inst:__len()
133         return len
134     end
135 
136     function inst:__index(k)
137         error("PriorityQueue: invalid member: " .. k)
138     end
139 
140     function inst:__newindex(k, v)
141         error("PriorityQueue: add member error: " .. k)
142     end
143 
144     setmetatable(inst, inst)
145     return inst
146 end
147 
148 function PriorityQueue.__call(self, compFunc)
149     return PriorityQueue.new(compFunc)
150 end
151 setmetatable(PriorityQueue, PriorityQueue)

测试代码：

 1 local function Test1()
 2     local q = PriorityQueue(function(a, b)
 3         return a > b
 4     end)
 5     assert(0 == q:count(), "count error")
 6     assert("" == tostring(q), "")
 7 
 8     q:push(3)
 9     assert(1 == q:count(), "push error")
10     assert("3" == tostring(q), "")
11 
12     q:push(1)
13     assert(2 == q:count(), "push error")
14     assert(3 == q:peek(), "peek error")
15     assert("3,1" == tostring(q), "")
16     
17     q:push(2)
18     assert(3 == q:count(), "push error")
19     assert(3 == q:peek(), "peek error")
20     assert("3,2,1" == tostring(q), "")
21 
22     assert(3 == q:pop(), "pop error")
23     assert(2 == q:count(), "pop error")
24     assert("2,1" == tostring(q), "")
25 
26     assert(2 == q:pop(), "pop error")
27     assert(1 == q:count(), "pop error")
28     assert("1" == tostring(q), "")
29 
30     assert(1 == q:pop(), "pop error")
31     assert(0 == q:count(), "pop error")
32     assert("" == tostring(q), "")
33 end
34 
35 Test1()

参考：

https://www.cnblogs.com/wxgblogs/p/5727026.html