堆排序之从无序序列创建初始堆

堆排序是一种常见的排序算法，其中一个重要的步骤就是从无序序列创建初始堆。这个过程也被称为堆化（heapify）。

具体的实现步骤如下：

1. 从最后一个非叶子节点开始，依次向上遍历整棵树。最后一个非叶子节点的位置为 n/2-1，其中n为序列的长度。

2. 对于当前遍历到的节点，如果它的值小于左子节点或右子节点的值，那么将当前节点的值与左右子节点中最大的一个进行交换。

3. 继续向上遍历，直到根节点。

4. 这样就完成了从无序序列创建初始堆的过程。

需要注意的是，在这个过程中，我们并不需要真正地构建一棵树，只是逻辑上将序列看成一棵完全二叉树进行操作。同时，这个过程的时间复杂度为 O(n)，其中 n 为序列的长度。

相关问题

设初始无序序列（36，48，48，90，88，80，76，99），求使用堆排序的方法建立的初始大顶堆，请画出该大顶堆。

以下是使用堆排序方法建立的初始大顶堆的示例：

初始无序序列：（36，48，48，90，88，80，76，99）

大顶堆的建立过程如下：

1. 从最后一个非叶子节点开始，向上调整每个子树，使其满足大顶堆的性质。
- 最后一个非叶子节点的索引为 n/2-1，其中 n 是序列的长度。
- 对于初始无序序列，最后一个非叶子节点的索引为 3。

2. 从最后一个非叶子节点开始，依次向上调整每个子树，使其满足大顶堆的性质。
- 每次调整的过程是将当前节点与其左右子节点中的较大值进行比较，如果当前节点小于较大值，则交换两者的位置。
- 调整完成后，继续向上调整父节点，直到根节点。

下面是大顶堆的建立过程：

初始无序序列：（36，48，48，90，88，80，76，99）

第一次调整：
         36
       /    \
     48      48
    /  \    /  \
  90   88  80   76
  /
99

第二次调整：
         36
       /    \
     48      99
    /  \    /  \
  90   88  80   76
  /
48

第三次调整：
         99
       /    \
     48      90
    /  \    /  \
  36   88  80   76
  /
48

第四次调整：
         99
       /    \
     88      90
    /  \    /  \
  36   48  80   76
  /
48

大顶堆建立完成。