Priority queue with Max-Heap

Question

I'm studying with book "Introduction to Algorithms" and implemented PriorityQueue without existed Class.

I made a MaxHeap class with Array and made a PriorityQueue with my Heap class.

Actually code is working and refactored code I did my best,

but I'm beginner so I need feedback for anybody.

would you give me a opinion?

public class PriorityQueue { private Heap heap; public PriorityQueue(int[] src){ heap = new Heap(src); } public int size() { return heap.size(); } public int extractMax() throws Exception { if(heap.size() < 1) throw new Exception("heap underflow"); int max = heap.get(0); heap.set(0,heap.get(getLastIndex())); heap.decrementSize(); MaxHeapify(0); return max; } public int getMaximum() throws Exception { return heap.get(0); } private int getLastIndex(){ return heap.size()-1; } public void increaseKey(int idx, int key) throws Exception { if(idx >= heap.size()) throw new IndexOutOfBoundsException(); if(key < heap.get(idx)) throw new Exception("new key is smaller than exist value"); heap.set(idx,key); while(idx > 0 && heap.get(heap.getParentIndex(idx)) < heap.get(idx)){ swap(idx, heap.getParentIndex(idx)); idx = heap.getParentIndex(idx); } } public void add(int key) throws Exception { heap.checkCapacity(); heap.incrementSize(); increaseKey(heap.size()-1, key); } private void MaxHeapify(int idx) { if(idx < 0 || idx >= heap.size) throw new IndexOutOfBoundsException(); int leftIndex = heap.getLeftIndex(idx); int rightIndex = heap.getRightIndex(idx); int size = heap.size(); int largest = -1; int tmp = Integer.MIN_VALUE; // compare with leftNode if(leftIndex < size && heap.get(leftIndex) > heap.get(idx)) largest = leftIndex; else largest = idx; // compare with rightNode if(rightIndex < size && heap.get(rightIndex) > heap.get(largest)) largest = rightIndex; // swap if parentNode is bigger than child. if(largest != idx){ swap(idx,largest); // recursive call MaxHeapify(largest); } } private void swap(int from, int to) { int tmp; tmp = heap.get(from); heap.set(from,heap.get(to)); heap.set(to,tmp); } public String toString(){ return Arrays.toString(heap.array); } public class Heap { int[] array = {}; int size; public Heap(int[] src){ array = src; size = array.length; } public Heap(){ array = new int[10]; size = array.length; } public int getLeftIndex(int idx){ return 2*idx+1; } public int getRightIndex(int idx){ return 2*idx+2; } public int getParentIndex(int idx){return idx/2;} // heap's size public int size(){ return size; } // array's size public int length(){ return array.length; } public void incrementSize(){ size++; } public void decrementSize(){ size--; } public int get(int idx) { return array[idx]; } // if heap's size is bigger than array's length, grow array's size; private void checkCapacity() { int oldCapacity = length(); if(size >= oldCapacity){ int newCapacity = oldCapacity + 10; array = Arrays.copyOf(array, newCapacity); } } public int[] getHeap(){ return array; } public boolean isValid(int idx){ return size-1 >= idx ? true : false; } public void set(int idx, int value) { if(isValid(idx)){ array[idx] = value; return; } throw new IndexOutOfBoundsException(); } } } 

Answer 1

For your coding style, that's good that I'm not the only one to use Guard Clauses, to clear the invalid states before entering the main code. Also, the methods are short and well named; I had no issues to find the code quickly, that's a big plus, in my opinion.

Minor issues

Method MaxHeapify

• The name of the method should start with a lowercase.
• The variable tmp is unused.

Method swap

• The variable tmp can be on the same line as the initialization.

 private void swap(int from, int to) { int tmp = heap.get(from); heap.set(from, heap.get(to)); heap.set(to, tmp); } 

Class Heap

• The initialization of the variable array with the value {} is useless, since the value is overridden in the constructor.

 public class Heap { //[...] int[] array; int size; //[...] { 

Method Heap#isValid

• The logic can be simplified.

 public boolean isValid(int idx) { return size - 1 >= idx; } 

Good job!