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();
    }
}