High level description of a priority queue with adjustable priority

Question

While implementing Dijkstra's and Prim's algorithms, we require a priority queue with adjustable priorities. I Understand how an array based implementation of the heap functions, but I don't understand how to make the priorities adjustable. I've read that a hashmap allows this, but I don't understand how.

Can someone please give me a high level description of this implementation using a hashmap using an example. a,b,c,d,e,f have priorities 2,4,0,6,1,9 respectively, how would I keep a track of their indices after insertion into the heap? if b's priority is changed to 8 how would this work?.

Please refer me to any additional material I may require to understand this.

Answer 1

import java.util.HashMap;
import java.util.NoSuchElementException;

public class Heap<Key extends Comparable<Key>> {
    private Key[] heap;
    private int maxN, n;
    private HashMap<Key, Integer> map;
    @SuppressWarnings("unchecked")
    public Heap(int maxN) {
        if(maxN < 0 ) throw new IllegalArgumentException();
        this.maxN = maxN;
        n = 0;
        heap = (Key[]) new Comparable[maxN];
        map = new HashMap<>(maxN);
    }

    boolean isEmpty() {
        return n == 0;
    }

    boolean insert(Key e) {
        if(n +1 > maxN) throw new IllegalArgumentException("maximum capacity reached " + maxN);
        heap[n] = e;
        map.put(e,n);
        int i = n++;
        swim(i);
        return true;
    }

    Key extractMin() {
        if(n == 0) throw new NoSuchElementException("Priority queue underflow ");
        Key min = heap[0];
        swap(0, n-1);
        map.remove(min);
        n--;
        sink(0);
        return min;
    }

    void delete(Key e){
        if(!map.containsKey(e)) return; //throw new NoSuchElementException(e+" does not exist ");
        int j = map.get(e);
        swap(j, n-1);
        map.remove(e);
        n--;
        if(!swim(j))
            sink(j);
    }

    void decreasePriority(Key e){
        if(map.containsKey(e)){
            int j = map.get(e);
            swim(j);
        }
        else insert(e);
    }

    private void swap(int i, int j) {
        Key t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
        map.replace(heap[i], i);
        map.replace(heap[j], j);
    }
    private boolean swim(int j){
        boolean change = false;
        int parent;
        while( (parent = (j-1)/2 ) >= 0){
            if(heap[j].compareTo(heap[parent]) < 0){
                swap(j,parent);
                j = parent;
                change = true;
            }
            else break;
        }
        return change;
    }
    private void sink(int j){
        while(j <= n/2 - 1){
            int leftChild = j*2 + 1, rightChild = leftChild + 1, s;
            if(rightChild >= n)
                s = leftChild;
            else
                s = heap[leftChild].compareTo(heap[rightChild]) < 0 ? leftChild : rightChild;
            if(heap[j].compareTo(heap[s]) > 0){
                swap(j,s);
                j = s;
            }
            else break;
        }
    }

    @Override
    public String toString() {
        String res = "[";
        int i;
        for (i = 0; i < n-1; i++){
            res += heap[i] + ", ";
        }
        res += heap[i]+"]";
        return res;
    }
}