Java中關于大頂堆的系列操作

IHeap.java

public interface IHeap {
    //向下調整
    void adjustDown(int root,int len);
    //初始化建立大頂堆
    void initHeap(int[] array);
    //向上調整，從孩子節點開始調整
    void adjustUp(int child);
    //插入item到堆中
    void pushHeap(int item);
    //傳回堆頂元素，删除資料元素
    int popHeap();
    //傳回堆頂元素，不删除資料
    int getHeapTop();
    //堆排序
    void HeapSort();
    //列印堆
    void show();
}

           

TestHeap.java

import java.util.Arrays;

/*
TOPK 一百一個資料，找出其中最大的10個
 */
public class TestHeap implements IHeap {
    private int[] elem;
    private int usedSize;
    private final int DEFAULT_SIZE = 10;

    public TestHeap() {
        this.elem = new int[DEFAULT_SIZE];
        this.usedSize = 0;
    }

    @Override
    //向下調整
    public void adjustDown(int root, int len) {
        int parent = root;
        int child = 2 * parent + 1;
        while (child < len) {
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                child++;
            }
            //child肯定是最大值的下标
            if (elem[child] > elem[parent]) {
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }

        }
    }

    @Override
    //初始化建立大頂堆
    public void initHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
        //開始調整堆，每一顆子樹都需要調整
        for (int i = (elem.length - 1 - 1) / 2; i >= 0; i--) {
            adjustDown(i, this.usedSize);
        }
    }

    @Override
    //向上調整，從孩子節點開始調整
    public void adjustUp(int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    public boolean isFull() {
        if (this.usedSize == this.elem.length) {
            return true;
        }
        return false;
    }

    @Override
    //傳回堆頂元素，删除資料元素
    public void pushHeap(int item) {
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }
        this.elem[this.usedSize] = item;
        this.usedSize++;
        adjustUp(this.usedSize - 1);
    }

    //交換0号下标元素（堆頂）和最後一個下标元素
    //傳回堆頂元素，不删除資料
    @Override
    public int popHeap() {
        if (this.usedSize == 0) {
            throw new UnsupportedOperationException("堆為空");
        }
        int temp = elem[0];
        elem[0] = elem[usedSize - 1];
        elem[usedSize - 1] = temp;
        this.usedSize--;
        adjustDown(0, this.usedSize);
        return 0;
    }

    @Override
    //傳回堆頂元素，不删除資料
    public int getHeapTop() {
        if (this.usedSize == 0) {
            throw new UnsupportedOperationException("堆為空");
        }
        return this.elem[0];
    }

    @Override
    //堆排序
    //首先已經是大根堆，堆頭與堆尾交換，然後下來僅調整0号下标元素
    public void HeapSort() {
        int end = this.usedSize - 1;
        while (end > 0) {
            int temp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = temp;
            adjustDown(0, end);
            end--;
        }
    }

    @Override
    //列印堆
    public void show() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
}

           

TestDemo.java

public class TestDemo {
    public static void main(String[] args){
        TestHeap testHeap=new TestHeap();
        int[] array={1,2,3,4,5,6,7,8,9};
        testHeap.initHeap(array);
        testHeap.show();
        testHeap.pushHeap(10);
        testHeap.show();
        testHeap.popHeap();
        testHeap.show();
        testHeap.HeapSort();
        testHeap.show();
    }
}