Priority Queue - Groovy Implementation

Here it is :), Another data structure, implemented by me in Groovy as part of my Groovy learning practices. Priority Queue.

	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'

view raw gistfile1.groovy hosted with ❤ by GitHub