数据结构之堆底层实现的循序渐进

题外话

把没写的都补回来!

正题

堆

概念

堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，

大根堆:指根结点比左右孩子都大的堆

小根堆:指根结点比左右孩子都小的堆

性质

1.堆中某个节点的值总是不大于或不小于其父节点的值

2.堆总是一棵完全二叉树。

向上调整

将数组调整为大根堆:

1.从最后一颗子树开始调整,利用二叉树的性质找到最后一颗树的父亲节点 (i-1)/2

2.获取左右孩子的最大值和根节点比较,如果比根节点大就交换,并且继续向下调整

3.调整完结点之后,让结点下标减1,即可从下往上调整为大根堆,一直调整到0下标

底层代码实现及详解

public class HeapBottom {
//创建数组
    private int[] elem;
//计数数组元素个数
    public int usedSize;
    public HeapBottom()
    {
        this.elem=new int[10];
    }
    //初始化elem数组
     public void intElem(int[] array)
     {
         for (int i = 0; i < array.length; i++) {
             elem[i]=array[i];
             usedSize++;
         }
     }
    //创建大根堆
     public void createHeap()
     {

         for (int parent = (elem.length-1)/2; parent>=0 ; parent--) {
//向上调整
        siftDown(parent,usedSize);

         }
     }
     //向上调整
    private void siftDown(int parent,int len)
    {
//创建child为parent左子树
        int child=parent*2+1;
//child小于数组长度时
        while (child<len)
        {
//如果child+1也小于数组长度,并且左子树小于右子树
            if (child+1<len&&elem[child]<elem[child+1])
            {
//将右子树下标赋给左子树,此时child相当于右子树
                child=child+1;
            }
//如果右子树大于父亲结点
            if (elem[child]>elem[parent])
            {
//交换元素值

                swap(parent,child);

//并继续向下调整(因为刚交换完的结点不一定是交换后的最大值),将交换完的子树下标给到parent
                parent=child;
//让child为parent左孩子
                child=parent*2+1;
            }
//如果右子树不大于父亲节点,则退出
            else {
                break;
            }

        }

    }

//交换代码

private void swap(int i,int j)

{

int temp=elem[i];

elem[i]=elem[j];

elem[j]=temp;

}

//添加元素

public void push(int val)
{
    //判断是否满了,满了扩容
    if (isFull())
    {
        Arrays.copyOf(elem,elem.length*2);
    }
    //赋值给最后一个元素
        elem[usedSize]=val;
    //向上调整
    siftUp(usedSize);
    usedSize++;
}

public boolean isFull()
{
    return usedSize==elem.length;
}
//向上调整
public void siftUp(int child)
{
    int parent=(child-1)/2;
    while (child>0) {
        if (elem[child] > elem[parent]) {
            swap(child, parent);
            child = parent;
            parent = (child - 1) / 2;
        }
        else {
            break;
        }
    }
    }
//删除元素(数组0下标位置元素和最后一个元素互换位置,然后向上调整即可)
    public int  pop()
    {
//判断是否为空数组,空了返回-1(自定义异常也可以)
        if (empty())
        {
            return -1;
        }
//将删除元素记录下来
        int tmp=elem[0];
//互换位置
        swap(0,usedSize-1);
//数组元素数量-1
        usedSize--;
//向上调整
        siftDown(0,usedSize);
        return tmp;
    }
//判断是否为空
    public boolean empty()
    {
        return usedSize==0;
    }

}