欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆排序(HeapSort)详解

程序员文章站 2022-06-06 23:40:33
...

1、什么是堆?

  • 堆是一个数据结构:其每个节点的值,大于等于其左右孩子节点的值,且为一颗完全二叉树
  • 堆(一棵树)可以用数组来表示。

2、大顶堆,小顶堆?

  • 堆又称为:大顶堆;
  • 小顶堆:每个节点的值,小于等于其左右孩子节点的值,的完全二叉树。

用法区别:

  • 降序排序------使用小顶堆;[6,5,4,3,2,1,0]
  • 升序排序------使用大顶堆;[0,1,2,3,4,5,6]

3、堆用数组表示的特点?

  • 对于节点arr[i]来说:
    arr[2*i+1]表示它的左孩子节点
    arr[2*i+2]表示它的右孩子节点
  • 对于一个长度为len的堆来说:
    – 其“最深”“最右”的非叶子节点为:arr[len/2+1]

由以上特点我们可以得到堆的特性:

  • 大顶堆:arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+1]
  • 小顶堆:arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+1]

4、堆排序的基本思想

  1. 将待排序序列,构成一个大顶堆;此时,最大值为根节点(索引=0)
  2. 将最大值与末尾元素交换;
  3. 将剩余的len-1个元素,继续构造成一个大顶堆;
  4. 重复以上2~3步骤、

5、具体实现方法:

(a)首先,构造一个大顶堆:

  1. 找到那个“最深”“最右”的非叶子节点;
  2. 从右至左,从上至下构建大顶堆,调用adjustHeap()方法;

adjustHeap(int[] arr, int i, int len)作用

  • 将以i为根节点、长度为len的数据,调整为一个大顶堆;

调用adjustHeap()方法的条件

  • 传入的以i为根节点的数据,必须要蛮子:只要将i与某个节点交换一轮位置,即可以得到一个大顶堆。

adjustHeap()方法的条件分析

  • 首先,那个“最深”“最右”的非叶子节点作为i,显然满足条件;其最多只有3个元素;
  • 其次,按照“从右至左,从上至下”的调整顺序,显然也满足条件;
  • 故该顺序调用adjustHeap()方法可以得到一个大顶堆;

那么,具体来说adjustHeap()方法是如何发挥作用的呢?
下面借助一个例子来帮助大家理解该方法的作用。
堆排序(HeapSort)详解
堆排序(HeapSort)详解堆排序(HeapSort)详解
完整:
堆排序(HeapSort)详解

(b)将最大值(索引=0)交换到最后

(c)调整以0为根节点的,大小为len-1的数据为大顶堆

  • 此时是满足调用adjustHeap()方法的条件的!!

(d)循环执行bc两步

5、代码以及注释:

	private void heapSort(int[] arr) {
        int len = arr.length;

        //1、首先,构造一个大顶堆:
        for(int i=len/2-1;i>=0;i--){
            //首先,这个最深的非叶子节点为根的结构,满足条件可以调用adjustHeap
            adjustHeap(arr,i,len);
            //然后,按照从右到左,从上到下的顺序调整(i--),就可以保证每个i都满足adjustHeap的条件
        }

        //2、循环:
        //      a.更换最大值(索引=0)和末尾元素(选择排序)
        //      b.调整前面len-1的结构为大顶堆
        for(int i = len-1; i > 0 ; i --){
            //把最大值放到末尾去
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            //调整前面的结构为大顶堆
            //此时,以0为根节点的结构,是可以直接调整的
            adjustHeap(arr,0,i);
        }
        // 调整完毕!
    }

    /**
     * 将符合条件的,以 i 为根节点的,长度为length的结构调整为堆!!
     *
     * @param arr    数组
     * @param i      要调整的根节点
     * @param length 要调整的数组长度
     */
    private void adjustHeap(int[] arr, int i, int length) {
        //把这个要调整的先放起来存着
        int temp = arr[i];
        //最开始的k是i的左节点
        //后面递归找自己的左节点
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            //首先,保证k指向的是i的左右节点里面最大的
            if(k+1 < length && arr[k] < arr[k+1]){
                k++;
            }
            if(arr[k] > temp){
                //如果这个“最大的左右子节点k”的值,他比我们现在的“根节点”更大,那么就得就换上去嘛;因为现在的k是左右子节点中的一个
                arr[i] = arr[k];
                //然后呢,要把i的位置也换到这个“最大的左右子节点k”上去;
                //这样做是为了下一层找下一个i的“最大的左右子节点k”
                i = k;
            }else {
                //如果现在这个“最大的左右子节点k”的值,小于等于之前的“根节点”的话呢;
                //说明当前的temp,放到k这一层的上一层就对了!(上一层要比下一层大或者等于)
                break;
            }
        }
        arr[i] = temp;
    }
相关标签: Java基础知识