数据结构-优先队列（堆）的实现

数据结构--优先队列（堆）的实现

1 优先队列是至少允许下列两种操作的数据结构：insert和deleteMin操作，insert相当于入队，deleteMin则相当于在优先队列中的出队。

2 我们使用二叉堆（这里也就叫做堆），来实现这种数据结构。堆有两个重要性质，其一是结构性，是一颗完全二叉树（高为h的二叉树有2exp(h)到2exp(h+1)-1个节点）

其二是对序性质，如果我们考虑任意一个字树也是一个堆，那么任意节点应该<它的所有孩子

上代码：

package com.itany.binarydui;

public class BinaryHeap<T extends Comparable<? super T>>
{
    //堆实际上是通过一个数组容器来实现的  每个元素的下标十分有意义
    private static final int DEFAULT_CAPACITY=10;
    private int currentSize;//堆中的元素个数
    private T[] array;//堆数组
    public int getCurrentSize()
    {
        return currentSize;
    }
    public BinaryHeap()
    {
        this(DEFAULT_CAPACITY);
    }
    public BinaryHeap(int capacity)
    {
        array=(T[])new Comparable[capacity];
    }
    
    //直接初始化时候就放入一个数组   不一个个insert
    public BinaryHeap(T[] arrayT)
    {
        currentSize=arrayT.length;
        array=(T[])new Comparable[(currentSize+2)*11/10];
        int i=1;
        for(T t:arrayT)
            array[i++]=t;
        buildHeap();//把这些数组传进来的数据  优化成二叉堆
    }
    
    public void makeEmpty()
    {
        currentSize=0;
        array=null;
    }
    public boolean isEmpty()
    {
        return currentSize==0;
    }
    public void insert(T t)
    {
        if(currentSize==array.length-1)
            enlargeArray(2*array.length+1);
        int hole=++currentSize;//创建一个空穴 再把空穴上浮
        //array[hole/2]就是array[hole]的父亲 不管hole是左儿子还是右儿子
        for(;hole>1 && t.compareTo(array[hole/2])<0;hole=hole/2)
        {
            //把大的父亲 拿到下面来  使hole变成父亲的大小  这样就避免了三个式子来进行交换
            array[hole]=array[hole/2];
        }
        array[hole]=t;//把空穴填上值
    }
    public T findMin()
    {
        return array[1];
    }
    public T deleteMin() throws Exception
    {
        if(isEmpty())
            throw new Exception();
        T minItem=findMin();
        //找出最小之后 还需要对堆的结构根据堆序进行调整
        //因为删除了一个 所以多出了一个空位子  我们把最后一个值 放到最上面去  然后再从数组序号1(原来的最后一个值)开始进行相应的比大小调整
        array[1]=array[currentSize--];
        percolateDown(1);
        return minItem;
    }
    //向下过滤 调整堆结构 使之满足堆序性要求
    private void percolateDown(int hole)
    {
        int child=0;//设置孩子的序号 child序号会不断改变
        //把 最上面的元素（不一定是最小的）先存储起来，因为如果它小的话 顶部的值会被下面的值给取代  等到Hole找到合适的位子时候 再把temp放到Hole里面去
        T temp=array[1];
        //currentSize>=2*hole表示当前hole有孩子时候就会继续进行下沉比较  如果没有孩子了 则比较结束 再给hole赋值
        for(;currentSize>=2*hole;hole=child)
        {
            //每循环一次 child都要至少*2
            child=2*hole;
            //child!=currentSize表示还有右孩子 且右孩子比较小 那么 此时应该array[hole]和右孩子进行比较  否则就和左孩子比较
            if(child!=currentSize && array[child].compareTo(array[child+1])>0)
                child++;
            if(array[hole].compareTo(array[child])>0)
                array[hole]=array[child];
            else
                break;
        }
        array[hole]=temp;
    }
    //建造一个堆
    private void buildHeap()
    {
        for(int i=currentSize/2;i>=1;i--)
        {
            percolateDown(i);//对每一个父节点进行堆序优化
        }
    }
    //扩大数组
    private void enlargeArray(int newSize)
    {
        T[] newArray=(T[])new Comparable[newSize];
        for(int i=0;i<array.length;i++)
        {
            newArray[i]=array[i];
        }
        array=newArray;
    }
    
}

package com.itany.binarydui;

public class Test
{
    
    public static void main(String[] args)
    {
//        BinaryHeap<Integer> bh=new BinaryHeap<Integer>();
//        bh.insert(50);
//        bh.insert(30);
//        bh.insert(40);
        Integer[] it={50,30,40};
        BinaryHeap<Integer> bh=new BinaryHeap<Integer>(it);

        System.out.println(bh.getCurrentSize());
        try
        {
            System.out.print(bh.deleteMin()+"  ");
            System.out.print(bh.deleteMin()+"  ");
            System.out.print(bh.deleteMin()+"  ");
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }

    }
    
}

数据结构-优先队列（堆）的实现

相关推荐