堆（一）最大堆和最小堆的實作

最大堆和最小堆的實作

這一講講的還是堆，是以将它歸入到堆（一）中。這一篇部落格的目的非常簡單，就是補充一下，堆的實作代碼。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);
        }
    }


}