gistfile1.groovy

class PriorityQueue {
    /*a list to contains the queue elments in a binary heap format*/
    def list = []
    
    /*Add new item to the queue*/
    def add(item) {
        list.add(item)
        
        /*After adding new item, we need to re-validate the heap*/
        siftUp(list, 0, list.size() - 1)
    }
    
    def pop() {
        if (list.isEmpty()) {
            return null
        } 
        def size = list.size()

        /*if there are maximum two items in the queue, we just return the first (root) item in the heap*/
        if (size < 3) {
            return list.remove(0)
        }
        
        /*Remove the first (root) item and move the last item to first place (root) in the list*/
        def item = list[0]
        list[0] = list.remove(size - 1)
        
        /*Revalidate the heap*/
        siftDown(list, 0, size - 2)
         
        return item
    }
    
    def peek() {
        if (list.isEmpty()) {
            return null
        }
        return list[0]
    }
    
    def isEmpty() {
        return list.isEmpty()
    }
    
    def size() {
        return list.size()
    }
    
    private siftDown(list, start, end) {
        def p = start
        
        while (p * 2 + 1 <= end) {
            /*Find the left side child*/
            def l = p * 2 + 1
            /*Find the right side child*/
            def r = l + 1
            /*Assume parent is the maximum value.*/
            def max = p
            
            /*If left child is bigger than parrent then keep it as max value*/
            if (list[max] < list[l]) {
                max = l
            }
            
            /*If right child exist and its bigger than others (parent and left child) then keep it as max value*/
            if (r <= end && list[max] < list[r]) {
                max = r
            }
            
            /*If parent is the the biggest value, then swap it with the biggest value*/
            if (p != max) {
                def t = list[p]
                list[p] = list[max]
                list[max] = t
                p = max
            } else  {
                break
            }
        } 
    }
    
    private siftUp(list, start, end) {
        def c = end
        
        while (c > start) {
            /*Find the parent node*/
            def p = (int)((end - 1) / 2)
            
            /*if the parent is less than child, then swap them*/
            if (list[p] < list[c]) {
                def t = list[p]
                list[p] = list[c]
                list[c] = t
                c = p
            } else {
                break
            }    
        }
    }
}

/****** Test ******/

def pq = new PriorityQueue()

assert true == pq.isEmpty(), 'the queue is empty'
assert 0 == pq.size(), 'the queue size should be 0'
assert null == pq.peek(), 'the queue is empty, so there should be nothing to peek'
assert null == pq.pop(), 'the queue is empty, so there should be nothing to pop'

pq.add(20)

assert false == pq.isEmpty(), 'quese is not empty anymore, there is one item (20) in the queue'
assert 1 == pq.size(), 'queue size must be 1'
assert 20 == pq.peek(), 'highest value in the queue is the 20'
assert 20 == pq.pop(), 'removing the highest value which is 20'
assert true == pq.isEmpty(), 'the queue is empty'
assert 0 == pq.size(), 'the queue size should be 0'

pq.add(20)
pq.add(30)
pq.add(50)

assert 50 == pq.peek(), 'the highest value must be 50'
assert 50 == pq.pop(), 'the highest value must be 50'
pq.add(10)

assert 30 == pq.peek(), 'the highest value must be 30'
assert 30 == pq.pop(), 'the highest value must be 30'