今天我们来谈谈堆

梦里梦外; 2021-12-09 05:25 203阅读 0赞

## 什么是堆 ##

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

*  堆是一个完全二叉树
 *  堆中每一个节点的值都必须大于等于（或小于等于）其子树中的值
    
    ## 最大堆 ##
    
    > 最大堆和最小堆是二查堆的两种形式,最大堆和最小堆很相似，所以本文只实现最大堆以及堆排序
 *  最大堆：根节点的键值是所有结点键值中的最大者，且每个结点的值都比孩子结点大  
    ![1450028-20190606215926081-431913338.png][]
 *  最小堆：根节点的键值是所有堆结点键值的最小者，且每个结点的值都比其孩子的值小。  
    ![1450028-20190606215935540-1696730038.png][]
    
    ## 索引关系 ##
    
    > 在最大堆中，设根节点索引从1开始，当父节点索引为i时，左子节点为2*i，右子节点为2*i+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;
    }

## 向堆里插入元素 ##

> 可以先将要插入的元素放在最后一个位置，然后与父元素比较、不断上移，直到该元素处于正确的位置  
> ![1450028-20190606215951522-1444407928.png][]  
> ![1450028-20190606215959090-538207994.png][]  
> ![1450028-20190606220010949-877950555.png][]  
> ![1450028-20190606220017279-2066963648.png][]

//堆插入元素时上移
        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();
            }
        }

转载于:https://www.cnblogs.com/wangbobobobo/p/10987047.html

[1450028-20190606215926081-431913338.png]: /images/20211209/6eeecea3aa8b4d76841fc3694cece82a.png
[1450028-20190606215935540-1696730038.png]: /images/20211209/a26e45bd8b874465abebf51465dc40e7.png
[1450028-20190606215951522-1444407928.png]: /images/20211209/3a57dd1b4ad74563b6eaa269ad532e75.png
[1450028-20190606215959090-538207994.png]: /images/20211209/ada2aeb709ca4c3abdcf1442999dbbf2.png
[1450028-20190606220010949-877950555.png]: /images/20211209/9b8046f43ca642a4a879ea9d4a4151bf.png
[1450028-20190606220017279-2066963648.png]: /images/20211209/cf7da1bb796c4699a13148b5460881dd.png