Heap的实现总结

HankerRank上对Heap的实现讲的很赞,再次贴下代码作为参考, 以min heap的实现为例, 我们用一个数组来放heap中的元素。
Min Heap的root节点总是最小值,所以获得最小值的时间复杂度为O(1),当root poll()出去后,heap中剩下的元素要进行调整,保证heap是min heap的结构,这个过程叫heapifyDown.
Poll(): 拿掉数组的第一个元素,对于第一个元素空出来的位置,先把数组最后一个元素放到 数组开头位置,然后进行heapifyDown进行调整,从root位置开始,比较root位置代表的parent与其左右children的大小,parent总是与children中元素较小的进行交换。 重复这个过程,直到大的元素不再有children。
Peek(): 返回数组的第一个元素的值。
Insert(): 插入一个新的元素,总是放在数组元素的最后一个位置,然后进行heapifyUp,调整heap满足min heap。
heapifyDown: 把最后一个元素放到root的位置,从root位置开始,比较root位置代表的parent与其左右children的大小,parent总是与children中元素较小的进行交换。 重复这个过程,直到大的元素不再有children。
heapifyUp: 数组新增的最后一个元素与其parent进行比较, 如果新增元素的值小于其parent的值,则进行交换,递归此过程。

import java.util.Arrays;

/**
 * Created by dylan on 10/29/16.
 * Reference: https://www.youtube.com/watch?v=t0Cq6tVNRBA
 */
public class MinIntHeap {
    private int capacity = 10;
    private int size = 0;

    int[] items = new int[capacity];

    private int getLeftChildIndex(int parentIndex) {return 2 * parentIndex + 1};
    private int getRightChildIndex(int parentIndex) {return 2 * parentIndex + 2};
    private int getParentIndex(int childIndex) {return (childIndex - 1) / 2;}

    private boolean hasLeftChild(int index) {return getLeftChildIndex(index) < size;}
    private boolean hasRightChild(int index) {return getRightChildIndex(index) < size;}
    private boolean hasParent(int index) {return getParentIndex(index) >= 0; }

    private int leftChild(int index) {return items[getLeftChildIndex(index)];}
    private int rightChild(int index) {return items[getRightChildIndex(index)];}
    private int parent(int index) {return items[getParentIndex(index)];}

    private void swap(int indexOne, int indexTwo) {
        int tmp = items[indexOne];
        items[indexOne] = items[indexTwo];
        items[indexTwo] = tmp;
    }

    private void ensureExtraCapacity() {
        if (size == capacity) {
            items = Arrays.copyOf(items, capacity * 2);
            capacity *= 2;
        }
    }

    public int peek() {
        if (size == 0) throw new IllegalStateException();
        return items[0];
    }

    public int poll() {
        if (size == 0) throw new IllegalStateException();
        int item = items[0]; // get the first element
        items[0] = items[size - 1]; // move the last element to the first element position
        size--;
        heapifyDown();
        return item;
    }

    public void add(int item) {
        ensureExtraCapacity();
        items[size] = item;
        size++;
        heapifyUp();
    }

    public void heapifyUp() {
        int index = size - 1; // start from last element
        while (hasParent(index) && parent(index) > items[index]) {
            swap(getParentIndex(index), index);
            index = getParentIndex(index);
        }
    }

    public void heapifyDown() {
        int index = 0; // start from root
        while(hasLeftChild(index)) {
            int smallerChildINdex = getLeftChildIndex(index);
            if (hasRightChild(index) && rightChild(index) < leftChild(index)) {
                smallerChildINdex = getRightChildIndex(index);
            }

            if (items[index] < items[smallerChildINdex]) {
                break;
            } else {
                swap(index, smallerChildINdex);
            }
            index = smallerChildINdex;
        }
    }

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s