function PriorityQueue.new()local J={}setmetatable(J,PriorityQueue)J:initialize()return J end function PriorityQueue.initialize(J)J.heap={}J.current_size=0 end function PriorityQueue.empty(J)return J.current_size==0 end function PriorityQueue.size(J)return J.current_size end function PriorityQueue.swim(J)local p=J.heap local A=floor local G=J.current_size while A(G/2)>0 do local J=A(G/2)if p[G][2]<p[J][2]then p[G],p[J]=p[J],p[G]end G=J end end function PriorityQueue.push(A,J,p)A.heap[A.current_size+1]={J,p}A.current_size=A.current_size+1 A:swim()end function PriorityQueue.sink(J)local p=J.current_size local A=J.heap local G=1 while G*2<=p do local p=J:min_child(G)if A[G][2]>A[p][2]then A[G],A[p]=A[p],A[G]end G=p end end function PriorityQueue.min_child(p,J)if J*2+1>p.current_size then return J*2 else if p.heap[J*2][2]<p.heap[J*2+1][2]then return J*2 else return J*2+1 end end end function PriorityQueue.pop(J)local p=J.heap local A=p[1][1]p[1]=p[J.current_size]p[J.current_size]=nil J.current_size=J.current_size-1 J:sink()return A end return PriorityQueue


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
