什么是堆

堆是一种特殊的树,他满足一下两点要求

  • 堆是一个完全二叉树
  • 堆中每一个节点的值都必须大于等于(或小于等于)其子树中的值

    最大堆

    最大堆和最小堆是二查堆的两种形式,最大堆和最小堆很相似,所以本文只实现最大堆以及堆排序

  • 最大堆:根节点的键值是所有结点键值中的最大者,且每个结点的值都比孩子结点大
  • 最小堆:根节点的键值是所有堆结点键值的最小者,且每个结点的值都比其孩子的值小。

    索引关系

    在最大堆中,设根节点索引从1开始,当父节点索引为i时,左子节点为2i,右子节点为2i+1

    数据结构

    堆的数据存储可以直接用数组存

private int[] data;
private int size;//当前堆的大小
private int capacity;//容量
public MaxHeap(int maxSize)
{
    data = new int[maxSize + 1];//下标从0开始
    this.size = 0;
    this.capacity = maxSize;
}

向堆里插入元素

可以先将要插入的元素放在最后一个位置,然后与父元素比较、不断上移,直到该元素处于正确的位置



//堆插入元素时上移
    private void shiftUp(int i)
    {
        while (i > 1 && data[i] > data[i / 2])
        {
            int temp = data[i];
            data[i] = data[i / 2];
            data[i / 2] = temp;
            i = i / 2;
        }
    }
//插入操作
    public void insert(int d)
    {
        if (size == capacity)
        {
            System.out.println("堆已满!");
            return;
        }
        data[++size] = d;
        shiftUp(size);
    }

删除堆中最大元素

最大堆删除操作只能删除最大元素,具体做法是将最后一个元素放到第一个位置,然后不断将其下移到适当位置

 //堆删除元素时下移
    private void shiftDown(int i)
    {
        while (2 * i <= size)
        {
            int j = 2 * i;//左子节点
            if (j + 1 <= size && data[j] < data[j + 1])
            {
                j++;
            }
            if (data[i] > data[j])
                break;
            //交换、下移
            int t = data[i];
            data[i] = data[j];
            data[j] = t;
            i = j;
        }
    }

    //删除堆顶,将最后一个移到堆顶,然后不断下移即可
    public int deleteMax()
    {
        if (size == 0)
        {
            System.out.println("堆空,不能删除...");
            return -1;
        }
        int t = data[1];//记录删除的值
        data[1] = data[size--];
        shiftDown(1);
        return t;
    }

堆排序

不断删除最大元素即可与实现堆排序

//堆排序,可以先将数组建成堆,然后依次删除最大元素
    public void heapSort(int arr[], MaxHeap heap)
    {
        for (int i = 0; i < arr.length; i++)
        {
            heap.insert(arr[i]);
        }
        //从小到大排序
        for (int i = arr.length - 1; i >= 0; i--)
        {
            arr[i] = heap.deleteMax();
        }
    }