「CS61B」Note(4) LAB10 Heap Min Priority Queue

/**
 * Returns the index of the node to the left of the node at i.
 */
private static int leftIndex(int i) {
    /* TODO: Your code here! */
    return 2 * i;
}

/**
 * Returns the index of the node to the right of the node at i.
 */
private static int rightIndex(int i) {
    /* TODO: Your code here! */
    return 2 * i + 1;
}

/**
 * Returns the index of the node that is the parent of the node at i.
 */
private static int parentIndex(int i) {
    /* TODO: Your code here! */
    return i / 2;
}

/**
 * Bubbles up the node currently at the given index.
 */
private void swim(int index) {
    // Throws an exception if index is invalid. DON'T CHANGE THIS LINE.
    validateSinkSwimArg(index);

    /** TODO: Your code here. */
    while (min(index, parentIndex(index)) == index && index != 1) {
        swap(index, parentIndex(index));
        index = parentIndex(index);
    }
}

/**
 * Bubbles down the node currently at the given index.
 */
private void sink(int index) {
    // Throws an exception if index is invalid. DON'T CHANGE THIS LINE.
    validateSinkSwimArg(index);

    /** TODO: Your code here. */
    while (getNode(leftIndex(index)) != null) {
        int minChildIndex = min(rightIndex(index), leftIndex(index));
        if (min(index, minChildIndex) == minChildIndex) {
            swap(index, minChildIndex);
            index = minChildIndex;
        } else break;
    }
}

private void swim(int index) {
    // Throws an exception if index is invalid. DON'T CHANGE THIS LINE.
    validateSinkSwimArg(index);

    /** TODO: Your code here. */
    if (min(index, parentIndex(index)) == parentIndex(index) || index == 1) {
        return;
    }
    swap(index, parentIndex(index));
    swim(parentIndex(index));
}

    private void sink(int index) {
    // Throws an exception if index is invalid. DON'T CHANGE THIS LINE.
    validateSinkSwimArg(index);

    /** TODO: Your code here. */
    if (getNode(leftIndex(index)) == null) {
        return;
    }
    int minChildIndex = min(rightIndex(index), leftIndex(index));
    if (min(index, minChildIndex) == index) {
        return;
    }
    swap(index, minChildIndex);
    sink(minChildIndex);
}

/**
 * Inserts an item with the given priority value. This is enqueue, or offer.
 * To implement this method, add it to the end of the ArrayList, then swim it.
 */
@Override
public void insert(T item, double priority) {
    /* If the array is totally full, resize. */
    if (size + 1 == contents.length) {
        resize(contents.length * 2);
    }

    /* TODO: Your code here! */
    size += 1;
    contents[size] = new Node(item, priority);
    swim(size);
}

/**
 * Returns the Node with the smallest priority value, but does not remove it
 * from the heap. To implement this, return the item in the 1st position of the ArrayList.
 */
@Override
public T peek() {
    /* TODO: Your code here! */
    return getNode(1).item();
}

/**
 * Returns the Node with the smallest priority value, and removes it from
 * the heap. This is dequeue, or poll. To implement this, swap the last
 * item from the heap into the root position, then sink the root. This is
 * equivalent to firing the president of the company, taking the last
 * person on the list on payroll, making them president, and then demoting
 * them repeatedly. Make sure to avoid loitering by nulling out the dead
 * item.
 */
@Override
public T removeMin() {
    /* TODO: Your code here! */
    T minItem = getNode(1).item();
    contents[1] = null;
    swap(1, size);
    sink(1);
    size -= 1;
    return minItem;
}

/**
 * Change the node in this heap with the given item to have the given
 * priority. You can assume the heap will not have two nodes with the same
 * item. Check item equality with .equals(), not ==. This is a challenging
 * bonus problem, but shouldn't be too hard if you really understand heaps
 * and think about the algorithm before you start to code.
 */
@Override
public void changePriority(T item, double priority) {
    /* TODO: Your code here! */
    for (int i = 1; i < size + 1; i++) {
        Node node = contents[i];
        if (node.item().equals(item)) {
            if (priority > node.priority()) {
                node.myPriority = priority;
                sink(i);
            } else {
                node.myPriority = priority;
                swim(i);
            }
            return;
        }
    }
}

@Test
public void testChangePriority() {
    ExtrinsicPQ<String> pq = new ArrayHeap<>();
    pq.insert("c", 3);
    pq.insert("i", 9);
    pq.insert("g", 7);
    pq.insert("k", 4);
    pq.insert("a", 1);
    pq.insert("h", 8);
    pq.insert("e", 5);
    pq.insert("b", 2);
    pq.insert("j", 3);
    pq.insert("d", 4);

    System.out.println("pq after inserting 10 items: ");
    System.out.println(pq);

    pq.changePriority("b", 6);

    System.out.println("pq after changing priority: ");
    System.out.println(pq);

    int i = 0;
    String[] expected = {"a", "c", "j", "d", "k", "e","b", "g", "h", "i"};
    while (pq.size() > 1) {
        assertEquals(expected[i], pq.removeMin());
        i += 1;
    }
}