堆（一）最大堆和最小堆的实现

最大堆和最小堆的实现

这一讲讲的还是堆，因此将它归入到堆（一）中。这一篇博客的目的非常简单，就是补充一下，堆的实现代码。Heap是抽象类，它有两个子类，MaxHeap和MinHeap。至于它们的function，我不再赘述了，请看堆（一）堆排序。

Heap

Heap，代码如下，它是一个抽象的父类。其实只有两个方法，buildHeap和heapify。其中，heapify方法由子类重写，如果我没有记错的话，这就是模板方法模式。buildHeap的行为随着子类对heapify的实现，而有所不同。注意，下面三个文件都在一个package下。

package heap;

public abstract class Heap {
    int[] items;
    int heapSize;

    Heap(int capacity) {
        items = new int[capacity];
    }

    Heap(int[] items) {
        this.items = items;
        heapSize = 0;
        buildHeap();
    }

    // 根据Max或者Min而变化
    private void buildHeap() {
        heapSize = items.length;
        for (int i = heapSize/2-1; i > -1;i--) {
            heapify(i);
        }
    }

    // 根据Max或者Min而变化
    protected abstract void heapify(int i);

    int left(int i) {
        return 2*i+1;
    }
    int right(int i) {
        return 2*i+2;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        int size = 1;
        int i = 0;
        while (i < heapSize) {
            for (int j = i; j < i+size && j < heapSize;j++) {
                builder.append(items[j]);
                builder.append(' ');
            }
            builder.append('\n');
            i += size;
            size *=2;
        }
        return builder.toString();
    }
}
           

MinHeap

实现了minHeapify方法。

package heap;

public class MinHeap extends Heap{
    public MinHeap(int capacity) {
        super(capacity);
    }

    public MinHeap(int[] items) {
        super(items);
    }

    @Override
    protected void heapify(int i) {
        int l = left(i);
        int r = right(i);
        int smallest = i;
        if (l < heapSize && items[l] < items[smallest]) smallest = l;
        if (r < heapSize && items[r] < items[smallest]) smallest = r;
        if (smallest != i) {
            int tmp = items[smallest];
            items[smallest] = items[i];
            items[i] = tmp;
            heapify(smallest);
        }
    }
}
           

MaxHeap

package heap;

public class MaxHeap extends Heap {
    public MaxHeap(int capacity) {
        super(capacity);
    }

    public MaxHeap(int[] items) {
        super(items);
    }

    @Override
    protected void heapify(int i) {
        int l = left(i);
        int r = right(i);
        int largest = i;
        if (l < heapSize && items[l]>items[largest]) largest = l;
        if (r < heapSize && items[r]>items[largest]) largest = r;
        if (largest != i) {
            int tmp = items[i];
            items[i] = items[largest];
            items[largest] = tmp;
            heapify(largest);
        }
    }


}