heaps in java

1import java.util.PriorityQueue;
2
3public class MaxHeapWithPriorityQueue {
4
5    public static void main(String args[]) {
6        // create priority queue
7        PriorityQueue<Integer> prq = new PriorityQueue<>(Comparator.reverseOrder());
8
9        // insert values in the queue
10        prq.add(6);
11        prq.add(9);
12        prq.add(5);
13        prq.add(64);
14        prq.add(6);
15
16        //print values
17        while (!prq.isEmpty()) {
18            System.out.print(prq.poll()+" ");
19        }
20    }
21
22}

1
2In Java PriorityQueue can be used as a Heap.
3
4Min Heap
5PriorityQueue<Integer> minHeap = new PriorityQueue<>();
6
7
8Max Heap:
9PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

1public class BinaryHeap {
2     
3    private static final int d= 2;
4    private int[] heap;
5    private int heapSize;
6     
7    /**
8     * This will initialize our heap with default size. 
9     */
10    public BinaryHeap(int capacity){
11        heapSize = 0;
12        heap = new int[ capacity+1];
13        Arrays.fill(heap, -1);
14         
15    }
16     
17    /**
18     *  This will check if the heap is empty or not
19     *  Complexity: O(1)
20     */
21    public boolean isEmpty(){
22        return heapSize==0;
23    }
24     
25    /**
26     *  This will check if the heap is full or not
27     *  Complexity: O(1)
28     */
29    public boolean isFull(){
30        return heapSize == heap.length;
31    }
32     
33     
34    private int parent(int i){
35        return (i-1)/d;
36    }
37     
38    private int kthChild(int i,int k){
39        return d*i  +k;
40    }
41     
42    /**
43     *  This will insert new element in to heap
44     *  Complexity: O(log N)
45     *  As worst case scenario, we need to traverse till the root
46     */
47    public void insert(int x){
48        if(isFull())
49            throw new NoSuchElementException("Heap is full, No space to insert new element");
50        heap[heapSize++] = x;
51        heapifyUp(heapSize-1);
52    }
53     
54    /**
55     *  This will delete element at index x
56     *  Complexity: O(log N)
57     * 
58     */
59    public int delete(int x){
60        if(isEmpty())
61            throw new NoSuchElementException("Heap is empty, No element to delete");
62        int key = heap[x];
63        heap[x] = heap[heapSize -1];
64        heapSize--;
65        heapifyDown(x);
66        return key;
67    }
68 
69    /**
70     *  This method used to maintain the heap property while inserting an element.
71     *  
72     */
73    private void heapifyUp(int i) {
74        int temp = heap[i];
75        while(i>0 && temp > heap[parent(i)]){
76            heap[i] = heap[parent(i)];
77            i = parent(i);
78        }
79        heap[i] = temp;
80    }
81     
82    /**
83     *  This method used to maintain the heap property while deleting an element.
84     *  
85     */
86    private void heapifyDown(int i){
87        int child;
88        int temp = heap[i];
89        while(kthChild(i, 1) < heapSize){
90            child = maxChild(i);
91            if(temp < heap[child]){ heap[i] = heap[child]; }else break; i = child; } heap[i] = temp; } private int maxChild(int i) { int leftChild = kthChild(i, 1); int rightChild = kthChild(i, 2); return heap[leftChild]>heap[rightChild]?leftChild:rightChild;
92    }
93     
94    /**
95     *  This method used to print all element of the heap
96     *  
97     */
98    public void printHeap()
99        {
100            System.out.print("nHeap = ");
101            for (int i = 0; i < heapSize; i++)
102                System.out.print(heap[i] +" ");
103            System.out.println();
104        }
105    /**
106     *  This method returns the max element of the heap.
107     *  complexity: O(1)
108     */
109     public int findMax(){
110         if(isEmpty())
111             throw new NoSuchElementException("Heap is empty.");
112         return heap[0];
113     }
114      
115     public static void main(String[] args){
116         BinaryHeap maxHeap = new BinaryHeap(10);
117         maxHeap.insert(10);
118         maxHeap.insert(4);
119         maxHeap.insert(9);
120         maxHeap.insert(1);
121         maxHeap.insert(7);
122         maxHeap.insert(5);
123         maxHeap.insert(3);
124          
125         maxHeap.printHeap();
126         maxHeap.delete(5);
127         maxHeap.printHeap();
128          
129     }
130}
131