heap堆结构以及堆排序

堆的定义

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；

• 堆总是一棵完全二叉树。

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆是非线性数据结构，相当于一维数组，有两个直接后继。

堆使用数组保存

使用一个一维数组保存堆数据

堆顶位于index0位置，i位置的左孩子位于 2*i+1位置，右孩子位于2*i+2位置，父位置位于(i-1)/2位置

堆操作

pop：弹出堆顶元素并删除

push：加入一个元素

peek：查看堆顶元素

heapify：从index位置，往下看，不断的下沉，直到到达或者堆最后位置

heapInsert：新加进来的数，现在停在了index位置，依次往上移动直到适合位置结束

code

/**
 * title:Heap
 * description: 堆介绍及其相关操作
 * date: 2023/9/8
 * author: fooleryang
 * version: 1.0
 */
 
/**
 *  堆 也叫优先级队列，是一颗 完全二叉树，其次，堆分为大根堆和小根堆
 *      完全二叉树
 *
 *      大根堆：
 *          子树的根节点是子树的最大值
 *      小根堆：
 *          子树的根节点是子数的最小值
 *  使用一个数组来表示一个堆
 *
 *  堆操作：
 *      heapInsert：新加进来的数，现在停在了index位置，依次往上移动直到适合位置结束
 *      heapify：从index位置，往下看，不断的下沉，直到到达或者堆最后位置
 *      peek：查看堆顶元素
 *      pop：弹出堆顶元素并删除
 *      push：加入一个元素
 *  使用一个数组记录堆
 *  用heapSize控制堆大小,heapSize =0说明堆为空
 *
 */
public  class Heap {
    //大根堆
    //数组存放
   private int [] heap;
   //堆数据最大存储量
   private  final int limit;
   //堆大小
   private int heapSize;
 
   public Heap(int limit){
       this.limit  = limit;
       heap = new int[limit];
       heapSize = 0;
   }
 
   public boolean isEmpty(){
       return heapSize == 0;
   }
   public boolean isFull(){
       return heapSize == limit;
   }
   private void swap(int [] arr,int l,int r){
       int temp = arr[l];
       arr[l] = arr[r];
       arr[r] = temp;
   }
   /**
    * 功能：
    *   堆插入时调整
    *   即： 在arr数组中，插入元素的位置为index，现需要进行调整
    * 参数：
    *   arr：待调整的堆
    *   index：待调整位置
    * 步骤：
    *   如果当前index位置和父位置 （index-1）/2 比较
    *   大于则交换，继续比较，直到小于等于或者到达堆顶位置即0位置
    *   小于等于则停止
    * 关于 (index -1) /2
    *   完全二叉树的求父节点位置应该是 index/2
    *   但是这是建立在index从1开始时
    *   如果index从0开始，那么就是 (index -1) /2
    *   1,2,3,4,5,6,7 => index=7的父节点index => 7/2 = 3
    *   0,1,2,3,4,5,6 => index=5的父节点index => (6-1)/2 = 2
    */
   private void heapInsert(int [] arr,int index){
 
       //结束条件包含：
       //arr[index] == 父节点value
       //index 达到0位置  arr[0] arr[(0-1)/2 = 0]
       while (arr[index] > arr[(index -1) / 2]){
           swap(arr,index,(index-1)/2);
           index = (index -1) /2;
       }
   }
   /**
    * @Description: 从index开始节点下沉，直到index位置的孩子都比index小，或者已经没有孩子
    * @Param arr:堆
    * @Param index:开始下沉节点
    * @Param heapSize:堆大小
    * 关于孩子节点：
    *   完全二叉树，左孩子 2*i +1,右孩子 2*i+2
    */
   private void heapify(int [] arr,int index,int heapSize){
       //左孩子index
       int leftChildIndex = 2 * index + 1;
       //遍历条件：index还有孩子
       while (leftChildIndex < heapSize){
           //比较index的左右孩子，记录得到最大左右孩子的index
           //右孩子存在 并且 右孩子大于左孩子，返回右孩子index，否则返回左孩子index
           //右孩子不存在 返回左孩子index
           int largestIndex = leftChildIndex+11]?leftChildIndex+1:leftChildIndex;
           //如果孩子中最大的孩子小于等于index，则结束
           if(arr[largestIndex] <= arr[index])break;
           //交换
           swap(arr,largestIndex,index);
           //index节点下沉
           index = largestIndex;
           leftChildIndex = 2 * index +1;
       }
   }
 
   //新加入一个元素
   public void push(int value){
       //查看是否已经堆满
       if(heapSize == limit)
           throw new RuntimeException("heap is full");
       //将新加入的元素放到最后一个位置
       heap[heapSize] = value;
       //向上调整堆
       heapInsert(heap,heapSize);
       //堆增加
       heapSize++;
   }
 
   /**
    * @Description: 弹出堆顶元素
    * 思路：
    *   堆顶元素位置 0
    *   将堆顶元素与堆最后一个位置交换,堆长减一
    *   从新堆顶元素0进行下沉调整堆
    */
   public int pop(){
       int ans = heap[0];
       swap(heap,0,heapSize-1);
       heapSize--;
       heapify(heap,0,heapSize);
       return ans;
   }
 
   public int peek(){
       if(heapSize==0)return -1;
       return heap[0];
   }
 
    //test
    public static void main(String[] args) {
        Heap heap1 = new Heap(10);
        heap1.push(3);
        heap1.push(9);
        heap1.push(1);
        heap1.push(3);
        heap1.push(5);
        heap1.push(0);
        heap1.push(6);
 
        while (!heap1.isEmpty()){
            System.out.print(heap1.pop() + " ");
        }
    }
 
 
}

构建堆图示

1. 已经构建好的堆

2. 新加入元素

3. 弹出堆顶元素

堆排序

时间复杂度 O(N*logN)

思路

待排序数组arr，将arr视作一个待排序的堆

先将arr构建成一个大根堆

再将大根堆arr调整为从小到大的顺序

构建大根堆过程

思路一

遍历arr数组

index = 0，arr 数组 0到index=0范围视为一个大根堆

index = 1，视为在0-0的大根堆加入一个元素，进行heapInsert操作

index = i，视为在0-（index-1）的大根堆加入元素

直到数组全部加入

for (int i = 0; i < arr.length; i++) {
    hearInsert(arr,i);
}

思路二

arr数组视为一个待排序堆，叶子结点分别构成的子树只有一个元素，天然为一个大根堆

依次往上构建的堆，则是需要调整，即新子树除了根节点其余子树都是大根堆，需要调整新子树的根节点，进行下沉调整

直到所有子树构建成一颗子树

如下图过程

1. 叶子结点分别为一个大根堆

2. 加入上层节点，需要进行下沉调整

3. 下沉调整

4. 继续步骤二 ，直到所有节点进入堆中

将大根堆数组调整到大小顺序

思路

将堆顶元素和最后一个元素交换，此时最大元素到达数组最后位置

将最后一个元素剔除堆

此时堆顶元素为待调整的元素，进行下沉调整

反复直到堆元素为空

int heapSize = arr.length;
do{
  swap(arr,0,--heapSize);// 等价与 swap(arr,0,heapSize-1);heapSize--;
  heapify(arr,0,heapSize);
}while (heapSize > 0);

code

    public static void heapSort(int [] arr){
        if(arr == null || arr.length < 2)return;
 
        //构建大根堆
 
        //从index = 0 开始
        //index = 0 ，则0-0为一个大根堆
        //inedx = 1，则将index=1插入到0-0堆中
        //index = i，则将index=i插入到0 到 (i-1)的堆中
        // O(N*logN)
//        for (int i = 0; i < arr.length; i++) {
//            hearInsert(arr,i);
//        }
 
        //或者这样调整，该步骤时间复杂度降低到O(N)
        //给定的数组是一个堆，只是顺序不对
        //从最低层即叶子节点开始下沉调整
        //最开始，叶子节点构成的子树为大根堆
        //上一层时，叶子节点构成的子树新加入一个节点并且位于子数的根节点，需要进行下沉调整
        //依次进行
        //O(N)
        for (int i = arr.length-1;i >=0;i--){
            heapify(arr,i,arr.length);
        }
 
        //将大根堆数组排序
 
        //将堆顶元素与数组最后一个元素交换
        //堆大小减一
        //交换完成后将堆顶元素下沉调整堆
//        int heapSize = arr.length;
//        swap(arr,0,heapSize-1);
//        heapSize--;
//        while (heapSize >0){
//            //调整
//            heapify(arr,0,heapSize);
//            swap(arr,0,heapSize-1);
//            heapSize--;
//        }
        int heapSize = arr.length;
        do{
            swap(arr,0,--heapSize);// 等价与 swap(arr,0,heapSize-1);heapSize--;
            heapify(arr,0,heapSize);
        }while (heapSize > 0);
    }
    private static void swap(int [] arr,int l,int r){
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
    //向下调整
    public static void heapify(int [] arr,int index,int heapSize){
        int left = index * 2 + 1;
        while (left < heapSize){
            int largest = left+1 < heapSize && arr[left+1] > arr[left]?left+1:left;
            if(arr[largest] < arr[index])break;
            swap(arr,index,largest);
            index = largest;
            left = index * 2 + 1;
        }
    }
 
    //插入一个新元素，向上调整
    public static void hearInsert(int [] arr,int index){
        int fatherIndex = (index - 1) / 2;
        while (arr[index] > arr[fatherIndex]){
            swap(arr,index,fatherIndex);
            index = fatherIndex;
            fatherIndex = (index - 1) / 2;
        }
    }