function PriorityQueue.new()local W={}setmetatable(W,PriorityQueue)W:initialize()return W end function PriorityQueue.initialize(W)W.heap={}W.current_size=0 end function PriorityQueue.empty(W)return W.current_size==0 end function PriorityQueue.size(W)return W.current_size end function PriorityQueue.swim(W)local q=W.heap local s=floor local h=W.current_size while s(h/2)>0 do local W=s(h/2)if q[h][2]<q[W][2]then q[h],q[W]=q[W],q[h]end h=W end end function PriorityQueue.push(s,W,q)s.heap[s.current_size+1]={W;q}s.current_size=s.current_size+1 s:swim()end function PriorityQueue.sink(W)local q=W.current_size local s=W.heap local h=1 while h*2<=q do local q=W:min_child(h)if s[h][2]>s[q][2]then s[h],s[q]=s[q],s[h]end h=q end end function PriorityQueue.min_child(q,W)if W*2+1>q.current_size then return W*2 else if q.heap[W*2][2]<q.heap[W*2+1][2]then return W*2 else return W*2+1 end end end function PriorityQueue.pop(W)local q=W.heap local s=q[1][1]q[1]=q[W.current_size]q[W.current_size]=nil W.current_size=W.current_size-1 W:sink()return s end return PriorityQueue
--[[setmetatable(
    PriorityQueue,
    {
        __call = function (self)
            setmetatable({}, self)
            self:initialize()
            return self
        end
    }
)]]

function PriorityQueue.new()
	local queueData = {}
	setmetatable(queueData, PriorityQueue)

	queueData:initialize()

	return queueData
end

function PriorityQueue:initialize()
	--[[  Initialization.
    Example:
        PriorityQueue = require("priority_queue")
        pq = PriorityQueue()
    ]]
	--
	self.heap = {}
	self.current_size = 0
end

function PriorityQueue:empty()
	return self.current_size == 0
end

function PriorityQueue:size()
	return self.current_size
end

function PriorityQueue:swim()
	-- Swim up on the tree and fix the order heap property.
	local heap = self.heap
	local floor = floor
	local i = self.current_size

	while floor(i / 2) > 0 do
		local half = floor(i / 2)
		if heap[i][2] < heap[half][2] then
			heap[i], heap[half] = heap[half], heap[i]
		end
		i = half
	end
end

function PriorityQueue:push(v, p)
	--[[ Put an item on the queue.
    Args:
        v: the item to be stored
        p(number): the priority of the item
    ]]
	--
	--

	self.heap[self.current_size + 1] = { v, p }
	self.current_size = self.current_size + 1
	self:swim()
end

function PriorityQueue:sink()
	-- Sink down on the tree and fix the order heap property.
	local size = self.current_size
	local heap = self.heap
	local i = 1

	while (i * 2) <= size do
		local mc = self:min_child(i)
		if heap[i][2] > heap[mc][2] then
			heap[i], heap[mc] = heap[mc], heap[i]
		end
		i = mc
	end
end

function PriorityQueue:min_child(i)
	if (i * 2) + 1 > self.current_size then
		return i * 2
	else
		if self.heap[i * 2][2] < self.heap[i * 2 + 1][2] then
			return i * 2
		else
			return i * 2 + 1
		end
	end
end

function PriorityQueue:pop()
	-- Remove and return the top priority item
	local heap = self.heap
	local retval = heap[1][1]
	heap[1] = heap[self.current_size]
	heap[self.current_size] = nil
	self.current_size = self.current_size - 1
	self:sink()
	return retval
end

return PriorityQueue
