CODEWITHSUNDEEP
javaalgorithmpriority-queue
FrancisGeek
FrancisGeek

Reputation: 147

The confusion of the index priority queue

I have got the idea of the priority queue.But when it comes to the index priority queue, I'm a little confused with the implemention of some method such as change(int k, Item item) and delete(int i) .

change(int k, Item item) is to change the item associated with k to item

delete(int i) is to remove k and its associated item

public void changeKey(int i, Key key) {
        if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        keys[i] = key;
        swim(qp[i]);
        sink(qp[i]);
    }

public void delete(int i) {
        if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        int index = qp[i];
        exch(index, n--);
        swim(index);
        sink(index);
        keys[i] = null;
        qp[i] = -1;
    }

private void swim(int k) {
        while (k > 1 && greater(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }

    private void sink(int k) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && greater(j, j+1)) j++;
            if (!greater(k, j)) break;
            exch(k, j);
            k = j;
        }
    }


private int maxN;        // maximum number of elements on PQ
private int n;           // number of elements on PQ
private int[] pq;        // binary heap using 1-based indexing
private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
private Key[] keys;      // keys[i] = priority of i

I understand the operation of sink and swim.But why in the method delete(int i) and changeKey(int i,Key key) have the statements swim(qp[i]/index); and sink(qp[i]/index);what on earth happens?

And I also want to know the elements construction style between priority queue and index priority queue and what is stored in the binary heap on the index priority queue?index or elements?

Upvotes: 3

Views: 6110

Answers (1)

Shadov
Shadov

Reputation: 5591

Those are operations on a binary heap that need to be performed when you change a key. Every 'node' in priority queue is kept in the binary heap. When you add an item, that item needs to be positioned in a right place, so the 'rules of binary heap' are not broken.

The same happens with changing the key, you need to change item's position in the priority heap so the rules are not broken (the children of that item are not bigger than it, and parent of that item is not smaller).

This priority queue is implemented with a binary heap, that means that it's based on binary tree, that's why you can see division by 2 in those methods, because it needs to take item up/down level by level and that is achieved by that division (first level has one node, second level has two nodes, third level has four nodes etc., number of nodes is multiplied by 2 each level).

This post is just an introduction to a huge and wide topic, I suggest reading more about it (especially 'heapify' sections): check this out.

Generally, the point is you have only 1 method for changing key and it invokes both swim and sink, because the previous key may be higher or lower. It's usually done with 2 methods: decreaseKey and increaseKey, and each of those methods calls only one - sink or swim, accordingly. Your code has those 2 methods combined into 1, that's why it calls both sink and swim. When the new key is higher than the old key that means it needs to go up in a heap (swim) and when the new key is lower than the old key it needs to go down (sink).

BTW my whole post is assuming we are working with maximum heap - that means that the root node has maximum value and his children have smaller value etc. There is also a minimum heap which is an exact opposite.

Upvotes: 7

Related Questions