堆与堆排序

注意阅读本文前应掌握树的基本知识

堆的定义

堆也称之为优先队列，根据其优先级细分为各种堆(队列)
常见的堆有两种，一种叫大根堆，一种叫小根堆

大根堆：需要符合以下条件

在完全二叉树中，任意一个子树的根节点都是该子树的最大值

小根堆：需要符合以下条件

在完全二叉树中，任意一个子树的根节点都是该子树的最小值

我们需要实现一个堆，才能进行堆排序

堆的实现

在这里我们用一个数组来表示一个堆（此处为大根堆）,学过树都知道，数组就可以表示树了

左边为完全二叉树形式，右边为大根堆形式，红色的数字代表对应的下标

可以从上图看出

进入一棵完全二叉树是：一直从左到右的，左子树满了，就去右子树，两颗子树都满了，就从左子树往下一层（左右子树的层数最多差一层）。

而进入一个大根堆则要在上面的插入规则的基础上再加上一条原则：我们把新插入的元素设置为，要与父节点比较大小

如果小于父节点则不用动完成插入操作

如果大于父节点则与父节点交换，并在父节点上进行同样的比较操作（与祖父节点比较），直到堆顶（arr[0]）或者小于其父节点则完成插入操作

此处涉及要求父节点的位置，这里我们直接给出公式,为了方便其他的操作我们同时给出求子节点的公式，求这两个公式并不难，兄弟萌可用纸笔算一。

父节点的位置：

(index - 1) / 2

子节点的位置 :

左节点：(index * 2) + 1
右节点：左节点 + 1

下面来看看插入部分代码的实现

public static void heapInsert(int[] arr, int index) {
    while(arr[index] > arr[(index - 1) / 2]) { //
        swap(arr,index,(index - 1) / 2);    //大于父节点就交换
        index = (index - 1) / 2;//去到父节点，再检查检查
    }
}

此处swap为交换数组中两值

删除操作很简单这里就不写了，这里我们讲另一个重要的操作heapify。

我们堆中的数值是可以变的，当我们把其中一个父节点变成小于其子节点的值，那么这将会破坏掉大根堆的性质，为了保持大根堆的性质，我们进行一个操作叫做heapify

当改变的节点的两个子节点均小于它的话，不用动

当改变的节点小于子节点中较大的一个，则进行”下沉”，下沉是指把左右子树中的较大者与当前节点进行比较，若大于当前节点则两者交换，并且进入下一层进行检查

heapify过程图解

下面来看看heapify代码的实现

public static void heapify(int[] arr, int index, int heapSize) {

    int left = index * 2 + 1;//右子树越界就等于不存在右子树
    while(left < heapSize) {//左子树不越界
        //求左右子树中哪个较大
        //右子树不越界且大于左子树的话largest就是左子树的位置为较大者
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left]
                ? left + 1 : left;
        //左右子树的最大值和当前节点的值谁大，返回较大者的下标
        largest = arr[largest] > arr[index] ? largest : index;
        if(largest == index) {//当前节点是最大的，不用下沉
            break;
        }
        //largest != index
        swap(arr, largest, index);//下沉
        //继续检查是否需要下沉
        index = largest;
        left = index * 2 + 1;
    }
}

可能会有兄弟萌问：为什么要用heapSize这个变量啊，我直接arr.length作为控制越界的变量不就行了，答曰：这里是为堆排序埋下伏笔。

堆排序

有了前面对堆的了解我们就可以开始学习堆排序了

堆排序的思路：

把数放进大根堆中，然后把堆顶和堆底的值进行交换（这样最大值在最后辣）。这时候heapSize就有用了，heapSize-1 这样最后一个元素就不会在动了，然后用heapify把堆调整回一个大根堆，继续进行上面的操作直至heapSize == 0 即可。

heapSort过程图解

代码如下：

public static void heapSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        for(int i = 0 ; i < arr.length; i++) {
            heapInsert(arr,i);//把数组进入大根堆
        }
        int heapSize = arr.length;
        swap(arr,0, --heapSize);    //为什么这里是--heapSize呢，因为heapSize == arr.length，默认数组是0到heapSize - 1的
        while(heapSize > 0) {
            heapify(arr,0,heapSize);//重新整理为大根堆
            swap(arr, 0, --heapSize);
        }
    }

插入的时间复杂度:O(logN)

因为在插入的时候你只需要不断的和父节点比较就行了，不用管其他节点，而且是完全二叉树，只需要树的高度的次数就行了
那么插入N次就需要：log1 + log2 + log3 + ... + logN-1
因此建立一个大根堆的时间复杂度是O(N)

稳定性：

不稳定，很简单可以想象到，堆顶的值和其子节点是相等的，而堆顶和堆底进行交换后，堆顶的值就去到最后了，和它相同的值与其的先后顺序改变了

堆及堆排序

堆与堆排序

堆的定义

堆的实现

堆排序

本章完结~