heap 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

1Whenever an object is created, it’s always stored in the Heap space, and stack
2memory contains the reference to it. Stack memory only contains local
3primitive variables and reference variables to objects in heap space.
4Objects stored in the heap are globally accessible whereas stack memory can’t 
5be accessed by other threads.
6Memory management in stack is done in LIFO manner whereas it’s more complex in
7Heap memory because it’s used globally.
8Stack memory is short-lived whereas heap memory lives from the start till the
9end of application execution.
10Heap memory is used by all the parts of the application, stack memory is used
11only by one thread of execution.
12When stack memory is full, Java runtime throws
13java.lang.StackOverFlowError When heap memory is full, it throws
14java.lang.OutOfMemoryError: Java Heap Space error.
15Stack memory is faster than heap memory.