井号层序遍历序列表示的树

你提供的 {5,4,#,3,#,2,#,1} 是一种用井号（#）表示空节点的层序遍历序列表示的二叉树。这种表示方法也称为序列化二叉树，常用于LeetCode等编程题中。

具体解释：

这个序列按层序遍历（广度优先）的顺序列出节点，用 # 表示空节点（即无子节点）。构建树时，我们需要逐层填充节点，遇到 # 则表示该位置没有节点。

你的例子：`{5,4,#,3,#,2,#,1}`

根节点：第一个元素 5 是根节点。
1
5
第二层：接下来的两个元素 4 和 # 是根节点的左右孩子。

4 是左孩子。
# 表示右孩子为空。
1
2
3
5
/
4

第三层：4 的左右孩子是接下来的两个元素 3 和 #。

3 是左孩子。
# 表示右孩子为空。
1
2
3
4
5
5
/
4
/
3

第四层：3 的左右孩子是 2 和 #。

2 是左孩子。
# 表示右孩子为空。
1
2
3
4
5
6
7
5
/
4
/
3
/
2

第五层：2 的左右孩子是 1 和 #。

1 是左孩子。
# 表示右孩子为空。
1
2
3
4
5
6
7
8
9
5
/
4
/
3
/
2
/
1

最终树的结构：

5
/
4
/
3
/
2
/
1

这是一个退化的二叉树（实际是一条向左倾斜的链表）。

注意事项：

这种表示法通常用大括号 {} 或方括号 [] 包裹，并用逗号分隔。
完整的层序遍历会包含所有空节点，直到最后一层。例如：

{5,4,#,3,#,2,#,1,#,#,#,#,#} 会更明确地表示所有空节点。

如果省略后续的 #（如你的例子），通常默认为省略了最后一层的所有空节点。

这种表示法适合快速输入/输出，但在实际构建树时需要按层序规则处理。

将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在第一轮排序结束之后，数组的顺序是_____。

解释：升序排列的题意就是大顶堆，降序就是小顶堆，原地进行的意思就是直接在原数组上模拟堆结构（利用数组下标关系表示父子节点），无需额外空间存储堆

6-5-3-2-4-1-7

如何使用数组模拟堆结构？

如何使用数组模拟堆结构

堆（Heap）是一种完全二叉树,可以用数组高效表示，无需显式构建树节点。以下是数组模拟堆结构的核心方法，包括父子节点关系、堆化（Heapify）操作、插入与删除等，并提供代码示例（Python/Java/C++）。

1. 数组表示堆的核心规则

(1) 下标关系（假设数组从 `0` 开始索引）

节点关系	计算公式
父节点	`(i - 1) // 2`
左子节点	`2 * i + 1`
右子节点	`2 * i + 2`
解释：理解起来有点复杂，节点 `i` （因为数组从 `0` 开始，实际是第i+1个节点，故）前面有 `i` 个节点，每个节点有 2 个子节点，由于前面节点的子节点一定在节点`i`的子节点前面，节点`i`后面节点的子节点一定在节点`i`的子节点后面，所以左孩子前面有且只有`2i`个节点，即位置是 `2 * i + 1`右孩子位置是 `2 * i + 2`？（同层的`i`右边的节点是上一层的子节点，它们也要算在节点`i`左子节点的前面，因为层数更低）

换言之，等效层序遍历，

左子节点、右子节点可以反推父节点公式，设节点i的父节点是p，如果i分别是左右子节点则分别有 i=2p+1（i满足奇数在左子节点）,i=2p+2（i是偶数在右子节点）

得到p = (i-1)//2

(2) 完全二叉树的性质

除最后一层外，其他层必须填满，且最后一层从左到右填充。
数组的连续存储对应树的层级遍历（广度优先）。

示例：
数组 [7, 6, 3, 5, 4, 1, 2] 表示的堆结构：

7 (0)
/\
6 (1)3 (2)
/\/\
5(3) 4(4) 1(5) 2(6)

2. 堆的基本操作

(1) 堆化（Heapify）

将无序数组调整为堆（大顶堆或小顶堆）。
步骤：

从最后一个非叶子节点（n//2 - 1）开始，向前遍历。
对每个节点，递归调整其子树以满足堆性质。

代码（大顶堆）：

def heapify(arr, n, i):
    largest = i          # 当前节点
    left = 2 * i + 1     # 左子节点
    right = 2 * i + 2    # 右子节点

    # 找到父节点、左子、右子中的最大值
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是当前节点，则交换并继续调整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)  # 递归调整受影响子树

(2) 构建堆（Build Heap）

将无序数组初始化为堆。
步骤：

从最后一个非叶子节点开始，向前调用 heapify。

代码：

def build_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):  # 从最后一个非叶子节点开始
        heapify(arr, n, i)

示例：
输入 [4, 10, 3, 5, 1] → 构建大顶堆后为 [10, 5, 3, 4, 1]。

3. 堆的插入与删除

(1) 插入元素（Insert）

将新元素添加到数组末尾。
从该节点向上调整（sift_up），直到满足堆性质。

代码：

def insert(heap, val):
    heap.append(val)
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] < heap[i]:  # 大顶堆：父节点 < 子节点则交换
            heap[parent], heap[i] = heap[i], heap[parent]
            i = parent
        else:
            break

(2) 删除堆顶（Extract Max/Min）

交换堆顶与末尾元素。
删除末尾元素（原堆顶）。
从新堆顶向下调整（heapify）。

代码：

def extract_max(heap):
    if not heap:
        return None
    max_val = heap[0]
    heap[0] = heap[-1]  # 末尾元素移到堆顶
    heap.pop()          # 删除末尾
    heapify(heap, len(heap), 0)  # 从堆顶向下调整
    return max_val

4. 堆排序（Heap Sort）

利用堆的性质实现原地排序（升序用大顶堆，降序用小顶堆）。
步骤：

构建初始堆（build_heap）。
交换堆顶与当前未排序部分的末尾元素。
调整剩余部分为堆，重复直到全部有序。

代码：

def heap_sort(arr):
	n = len(arr)
	# 构建初始大顶堆
	build_heap(arr)
	# 逐个提取堆顶元素（交换并调整）
	for i in range(n - 1, 0, -1):
		arr[0], arr[i] = arr[i], arr[0]# 交换堆顶和末尾
		heapify(arr, i, 0)# 调整剩余部分

示例：
输入 [7, 6, 3, 5, 4, 1, 2] → 排序后为 [1, 2, 3, 4, 5, 6, 7]。

6. 关键点总结

数组模拟堆的核心：利用下标关系表示父子节点。
堆化（Heapify）：从某个节点向下调整，时间复杂度 O(log n)。
原地性：堆排序仅需 O(1) 额外空间。
应用场景：

优先级队列（如 Dijkstra 算法）。
Top K 问题（用最小堆维护前 K 大元素）。
排序（堆排序时间复杂度 O(n log n)）。

通过数组模拟堆，可以高效实现动态数据的插入、删除和排序，而无需显式构建树结构！

不可能是第2趟快速排序结果

(2023_飞猪)假设一个数组采用快速排序进行升序排序，则下面的选项中，不可能是第2趟排序结果的是（）
A
20, 10, 5, 9, 7, 30, 35
B
1, 30, 5, 20, 15, 7, 31
C
20, 10, 15, 5, 11, 12, 13
D
5, 6, 9, 30, 35, 1, 10

思路：至少有两个元素，对于这两个元素，左边的都比它小，右边的都比他大，只需要遍历整个序列找到这两个元素即可，如果找不到则不可能。
注意升序VS降序：升序元素右边的都比它大，对于降序，只要找到两个元素，反过来，左边的都比它大，右边的都比他小