数据结构与算法（Java版）

完全二叉树叫做堆。

完全二叉树就是最后一个节点之前不允许有不满的节点，就是不允许有空洞。

可以使用数组来做完全二叉树（堆）。

堆分为大顶堆和小顶堆。大顶堆就是根节点上的数字是最大的，小顶堆就是根节点上的数字是最小的堆。

在堆里面的操作包括两种：插入新的节点和删除根节点。

插入新节点的操作时向上渗透。删除根节点的操作是向下渗透。

插入新节点时，把新的节点插入到最后一个位置，然后慢慢向上渗透（和父辈交换）。删除根节点时，把最后一个节点放到根节点上，然后再慢慢向下渗透（和子代交换）。

下面使用Java写一个大顶堆。

package Heap;

public class MaxHeap {

    private int[] heapArray;

    private int maxSize;

    private int currentSize;

    /*构造函数*/

    public MaxHeap(int mx) throws Exception {

        if(mx < 1) throw new Exception("max size must be >=1");

        maxSize = mx;

        currentSize = 0;

        heapArray = new int[maxSize];

    }

    /*向上渗透,index为下标*/

    private void trickleUp(int index){

        int parent = (index - 1) / 2;

        int bottom = heapArray[index];

        while(index>0 && heapArray[parent]<bottom){

            heapArray[index] = heapArray[parent];

            index = parent;

            parent = (parent - 1) / 2;

        }

        heapArray[index] = bottom;

    }

    /*向下渗透*/

    private void trickleDown(int index){

        int largerChild;

        int top = heapArray[index];

        while(index < currentSize / 2){

            int leftChild = 2 * index + 1;

            int rightChild = 2 * index + 2;

            if(rightChild<currentSize && heapArray[leftChild]<heapArray[rightChild])

                largerChild = rightChild;

            else

                largerChild = leftChild;

            if(top >= heapArray[largerChild])

                break;

            heapArray[index] = heapArray[largerChild];

            index = largerChild;

        }

        heapArray[index] = top;

    }

    public boolean IsEmpty(){

        return currentSize == 0;

    }

    public void Push(int num) throws Exception{

        if(currentSize == maxSize) throw new Exception("MaxHeap id full");

        heapArray[currentSize] = num;

        trickleUp(currentSize);

        currentSize++;

    }

    public int Top(){

        return heapArray[0];

    }

    public void Pop(){

        heapArray[0]=heapArray[--currentSize];

        trickleDown(0);

    }

    public static void main(String[] args) throws Exception {

        System.out.println("测试大顶堆");

        MaxHeap maxHeap = new MaxHeap(100);

        System.out.println(maxHeap.IsEmpty());

        maxHeap.Push(20);

        maxHeap.Push(30);

        maxHeap.Push(40);

        System.out.println(maxHeap.Top());

        maxHeap.Push(90);

        maxHeap.Push(80);

        maxHeap.Push(70);

        System.out.println(maxHeap.Top());

        maxHeap.Pop();

        System.out.println(maxHeap.Top());

        maxHeap.Pop();

        System.out.println(maxHeap.Top());

        maxHeap.Pop();

        System.out.println(maxHeap.Top());

    }

}

堆排序就是迭代弹出栈顶元素。

堆排序的时间复杂度是O(nlogn).

巴特西

数据结构与算法（Java版）_堆

最新文章

热门文章