java数据结构与算法基础-----排序------堆排序

文章目录

1. 堆排序是利用堆（数据结构）设计的排序算法，属于选择排序，最坏，最好，平均时间复杂度均为O(n logn)，不稳定排序
2. 堆是具有以下性质的完全二叉树：

1. 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
2. 不对结点的左孩子的值和右孩子的值的大小关系进行要求。
3. 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
   
   

1. 堆排序，就是符合一定规则的完全二叉树，这个规则是：整个二叉树中，你随便挑出一颗子树，都满足根结点>=左右孩子（大根堆）或者根结点<=左右孩子(小根堆)
2. 所以如果我们采用从下往上构建堆，是比较方便的。只需要关注当前的子树满足指定规则即可
3. 例如我们想要构建一个长度为4的小顶堆，需要插入的元素是[3,2,3,1,2,4,5,5,6],我们想要实现，保留[3,2,3,1,2,4,5,5,6]中最大的4个在小顶堆中

1. 先无脑插入4个结点，因为我们的堆长度为4，heap=[3,2,3,1]
2. 然后调整堆，从第一个非叶子结点开始调整，利用完全二叉树公式len/2-1是第一个非叶子，len/2-2是第二个非叶子，依次类推

1. 第一个非叶子结点root为4/2 - 1 = 1,也就是heap[1] = 2. 然后根据完全二叉树公式获取其左右孩子，left = root * 2+1 和 right = root * 2+2。也就是left = 1 * 2+1 = heap[3] = 1.right = 1 * 2+2 = 4，超出堆大小，没有右孩子。
2. 此时我将让root和left以及right比较，谁小谁做根结点。发现root = heap[1] = 2 > left = heap[3] = 1.故root下降到left位置，left上升到root位置。
3. 从而堆变成heap = [3,1,3,2]
4. 第二个非叶子结点root为4/2-2 = 0,也就是heap[0] = 3, 其left = 0 * 2 +1 = heap[1] = 1.其right = 0 * 2+2 = heap[2] = 3.
5. 比较后发现，root>left,因此进行root下降到left操作，也就是交换位置swap(root,left)，此时heap = [1,3,3,2]
6. 然后发现此时root指向原来left位置，也就是下降一次后，root = heap[1] = 3，我们发现它还有一个左孩子left = 1 * 2+1 = heap[3] = 2. 我们发现root>left,因此root继续下降，此时heap = [1,2,3,3]

3. 堆构建完成后，我们进行插入操作，现在该插入第5个结点，[2]，我们发现[2]>堆顶的[1].因此[1]肯定不是序列中最大的4个中的一个，所以我们将堆顶元素heap[0] 换为 [2].然后重新回到上面的调整堆的操作。也就是不断下降的操作，直到[2]下降到符合小根堆的位置。
4. 依次类推，直到所有元素处理完成，就构建完成了一个小顶堆

1. 用到的公式(二叉树的基本公式)

1. arr[i]<=arr[2 * i+1] && arr[i] <= arr[2 * i+2] 小顶堆条件，当前非叶子节点arr[i]，左节点和右节点，都小于它,大顶堆正好相反，左右都大于它本身
2. 第一个非叶子节点arr.length/2-1
3. 当前节点的左子节点，i * 2+1，当前节点右子节点i * 2+2

直接实现小根堆难免让人不知道这是干什么用的，因此，用一道算法题来理解。这道题的代码完全就是小根堆的代码。