实现二叉堆 / 优先级队列
二叉堆的主要操作就两个，sink（下沉）和 swim（上浮），用以维护二叉堆的性质。
二叉堆的主要应用有两个，首先是一种很有用的数据结构优先级队列（Priority Queue），第二是一种排序方法堆排序（Heap Sort）。
能动态排序的常用数据结构其实只有两个，一个是优先级队列（底层用二叉堆实现），另一个是二叉搜索树。二叉搜索树的用途更广泛，优先级队列能做的事情，二叉搜索树其实都能做。但优先级队列的 API 和代码实现相较于二叉搜索树更简单，所以一般能用优先级队列解决的问题，我们没必要用二叉搜索树。
二叉堆的性质
你可以认为二叉堆是一种特殊的二叉树，这棵二叉树上的任意节点的值，都必须大于等于（或小于等于）其左右子树所有节点的值。如果是大于等于，我们称之为「大顶堆」，如果是小于等于，我们称之为「小顶堆」。
对于小顶堆，每个节点下方的所有节点的值都比它大，那么不难想象根节点就是整棵树上的最小值。同理，大顶堆的根节点就是整棵树上的最大值。所以二叉堆可以辅助我们快速找到最大值或最小值。
二叉堆还有个性质：一个二叉堆的左右子堆（子树）也是一个二叉堆。这个性质主要在 堆排序算法的优化 中有用到。
二叉堆的难点在于 你在插入或删除元素时，还要保持堆的性质
另外，自动排序是有代价的，注意优先级队列 API 的时间复杂度，增删元素的复杂度是 O(logN)，其中 N 是当前二叉堆中的元素个数
Push / swim
以小顶堆为例，向小顶堆中插入新元素遵循两个步骤：
1、先把新元素追加到二叉树底层的最右侧，保持完全二叉树的结构。此时该元素的父节点可能比它大，不满足小顶堆的性质。
2、为了恢复小顶堆的性质，需要将这个新元素不断上浮（swim），直到它的父节点比它小为止，或者到达根节点。此时整个二叉树就满足小顶堆的性质了。
// 创建一个小顶堆，并初始化一些元素在里面 let minHeap = Heap.createMin([1,6,8,2,10,13,0,7]); // 步骤一、把新节点插到完全二叉树的最下层 // 此时 parent.val > newNode.val，小顶堆的性质被破坏 let newNode = Heap.makeNode(4); // @visualize color newNode #137924 let parent = minHeap._getRoot().left.left; parent.right = newNode; newNode.parent = parent; // 步骤二、把新节点上浮到正确位置，维护小顶堆的性质 // 我们在后续代码实现中把这个过程称为 swim while (parent != null && parent.val > newNode.val) { // 让 newNode 节点向上浮 let temp = parent.val; parent.val = newNode.val; newNode.val = temp; newNode = parent; parent = parent.parent; } // 此时，小顶堆的性质恢复，元素插入完成 console.log('min heap recovered'); // 你可以修改 newNode 的值，查看插入过程
Pop / sink
以小顶堆为例，删除小顶堆的堆顶元素遵循两个步骤：
1、先把堆顶元素删除，把二叉树底层的最右侧元素摘除并移动到堆顶，保持完全二叉树的结构。此时堆顶元素可能比它的子节点大，不满足小顶堆的性质。
2、为了恢复小顶堆的性质，需要将这个新的堆顶元素不断下沉（sink），直到它比它的子节点小为止，或者到达叶子节点。此时整个二叉树就满足小顶堆的性质了。
// 创建一个小顶堆，并初始化一些元素在里面 let minHeap = Heap.createMin([1,6,8,2,4,10,13,0,7]); // 步骤一、把堆顶元素删除，把底层最右侧元素移动到堆顶 let topNode = minHeap._getRoot(); let bottomNode = topNode.left.left.right; // 摘除底部最右侧元素 let parent = bottomNode.parent; bottomNode.parent = null; if (parent.left === bottomNode) { parent.left = null; } else { parent.right = null; } // 删除堆顶元素，把底部最右侧元素放到堆顶 topNode.val = bottomNode.val; // 此时 topNode.val 大于子树节点的值，小顶堆的性质被破坏 // 步骤二、把新的堆顶元素下沉到正确位置，维护小顶堆的性质 // 我们在后续代码实现中把这个过程称为 sink let p = topNode; // @visualize color p #6194be while (p.left || p.right) { // 选择 p 的左右子节点中值较小的那个 let min = p; if (p.left !== null && p.left.val < min.val) { min = p.left; } if (p.right !== null && p.right.val < min.val) { min = p.right; } // 如果 p 的值已经比左右子节点都小，说明 p 已经在正确位置 if (min === p) break; // 否则的话，通过交换操作将 p 节点下沉 let temp = p.val; p.val = min.val; min.val = temp; p = min; } // 此时，小顶堆的性质恢复，堆顶元素删除完成 console.log('min heap recovered');
在数组上模拟
我们在代码实现的时候，不会用类似 HeapNode 的节点类来实现，而是用数组来模拟二叉树结构。
在数组的末尾追加元素，就相当于在完全二叉树的最后一层从左到右依次填充元素；数组中最后一个元素，就是完全二叉树的底层最右侧的元素
事实上，任何完全二叉树，都可以用代码来模拟 —— 按照层序遍历依次储存
父节点的索引 = (子节点索引 - 1) / 2
左子节点的索引 = 父节点索引 * 2 + 1
右子节点的索引 = 父节点索引 * 2 + 2
索引 0 空着不用
父节点的索引 = 子节点索引 / 2
左子节点的索引 = 父节点索引 * 2
右子节点的索引 = 父节点索引 * 2 + 1
package main import "fmt" type SimpleMinPQ struct { // 底层使用数组实现二叉堆 heap []int // 堆中元素的数量 size int } // 父节点的索引 func (pq *SimpleMinPQ) parent(node int) int { return (node - 1) / 2 } // 左子节点的索引 func (pq *SimpleMinPQ) left(node int) int { return node*2 + 1 } // 右子节点的索引 func (pq *SimpleMinPQ) right(node int) int { return node*2 + 2 } // 交换数组的两个元素 func (pq *SimpleMinPQ) swap(i, j int) { pq.heap[i], pq.heap[j] = pq.heap[j], pq.heap[i] } // 查，返回堆顶元素，时间复杂度 O(1) func (pq *SimpleMinPQ) Peek() int { return pq.heap[0] } // 增，向堆中插入一个元素，时间复杂度 O(logN) func (pq *SimpleMinPQ) Push(x int) { // 把新元素追加到最后 pq.heap[pq.size] = x // 然后上浮到正确位置 pq.swim(pq.size) pq.size++ } // 删，删除堆顶元素，时间复杂度 O(logN) func (pq *SimpleMinPQ) Pop() int { res := pq.heap[0] // 把堆底元素放到堆顶 pq.heap[0] = pq.heap[pq.size-1] pq.size-- // 然后下沉到正确位置 pq.sink(0) return res } // 上浮操作，时间复杂度是树高 O(logN) func (pq *SimpleMinPQ) swim(node int) { for node > 0 && pq.heap[pq.parent(node)] > pq.heap[node] { pq.swap(pq.parent(node), node) node = pq.parent(node) } } // 下沉操作，时间复杂度是树高 O(logN) func (pq *SimpleMinPQ) sink(node int) { for pq.left(node) < pq.size || pq.right(node) < pq.size { // 比较自己和左右子节点，看看谁最小 min := node if pq.left(node) < pq.size && pq.heap[pq.left(node)] < pq.heap[min] { min = pq.left(node) } if pq.right(node) < pq.size && pq.heap[pq.right(node)] < pq.heap[min] { min = pq.right(node) } if min == node { break } // 如果左右子节点中有比自己小的，就交换 pq.swap(node, min) node = min } } func main() { pq := SimpleMinPQ{ heap: make([]int, 5), // size: 0, } pq.push(3) pq.push(2) pq.push(1) pq.push(5) pq.push(4) fmt.Println(pq.pop()) // 1 fmt.Println(pq.pop()) // 2 fmt.Println(pq.pop()) // 3 fmt.Println(pq.pop()) // 4 fmt.Println(pq.pop()) // 5 }
优先级队列
package main import ( "fmt" "errors" ) type MyPriorityQueue struct { // 堆数组 heap []interface{} // 堆中元素的数量 size int // 元素比较器 comparator func(x, y interface{}) int } // 构造函数 func NewMyPriorityQueue(capacity int, comparator func(x, y interface{}) int) *MyPriorityQueue { return &MyPriorityQueue{ heap: make([]interface{}, capacity), size: 0, comparator: comparator, } } // 返回堆的大小 func (pq *MyPriorityQueue) Size() int { return pq.size } // 判断堆是否为空 func (pq *MyPriorityQueue) IsEmpty() bool { return pq.size == 0 } // 父节点的索引 func (pq *MyPriorityQueue) Parent(node int) int { return (node - 1) / 2 } // 左子节点的索引 func (pq *MyPriorityQueue) Left(node int) int { return node*2 + 1 } // 右子节点的索引 func (pq *MyPriorityQueue) Right(node int) int { return node*2 + 2 } // 交换数组的两个元素 func (pq *MyPriorityQueue) Swap(i, j int) { pq.heap[i], pq.heap[j] = pq.heap[j], pq.heap[i] } // 查，返回堆顶元素，时间复杂度 O(1) func (pq *MyPriorityQueue) Peek() (interface{}, error) { if pq.IsEmpty() { return nil, errors.New("priority queue underflow") } return pq.heap[0], nil } // 增，向堆中插入一个元素，时间复杂度 O(logN) func (pq *MyPriorityQueue) Push(x interface{}) { // 扩容 if pq.size == len(pq.heap) { pq.resize(2 * len(pq.heap)) } // 把新元素追加到最后 pq.heap[pq.size] = x // 然后上浮到正确位置 pq.swim(pq.size) pq.size++ } // 删，删除堆顶元素，时间复杂度 O(logN) func (pq *MyPriorityQueue) Pop() (interface{}, error) { if pq.IsEmpty() { return nil, errors.New("priority queue underflow") } res := pq.heap[0] // 把堆底元素放到堆顶 pq.Swap(0, pq.size-1) // 避免对象游离 pq.heap[pq.size-1] = nil pq.size-- // 然后下沉到正确位置 pq.sink(0) // 缩容 if pq.size > 0 && pq.size == len(pq.heap)/4 { pq.resize(len(pq.heap) / 2) } return res, nil } // 上浮操作，时间复杂度是树高 O(logN) func (pq *MyPriorityQueue) swim(node int) { for node > 0 && pq.comparator(pq.heap[pq.Parent(node)], pq.heap[node]) > 0 { pq.Swap(pq.Parent(node), node) node = pq.Parent(node) } } // 下沉操作，时间复杂度是树高 O(logN) func (pq *MyPriorityQueue) sink(node int) { for pq.Left(node) < pq.size { // 比较自己和左右子节点，看看谁最小 minNode := node if pq.Left(node) < pq.size && pq.comparator(pq.heap[pq.Left(node)], pq.heap[minNode]) < 0 { minNode = pq.Left(node) } if pq.Right(node) < pq.size && pq.comparator(pq.heap[pq.Right(node)], pq.heap[minNode]) < 0 { minNode = pq.Right(node) } if minNode == node { break } // 如果左右子节点中有比自己小的，就交换 pq.Swap(node, minNode) node = minNode } } // 调整堆的大小 func (pq *MyPriorityQueue) resize(capacity int) { newHeap := make([]interface{}, capacity) for i := 0; i < pq.size; i++ { newHeap[i] = pq.heap[i] } pq.heap = newHeap } func main() { pq := NewMyPriorityQueue(3, func(x, y interface{}) int { a := x.(int) b := y.(int) if a < b { return -1 } else if a > b { return 1 } return 0 }) pq.Push(3) pq.Push(1) pq.Push(4) pq.Push(1) pq.Push(5) pq.Push(9) // 1 1 3 4 5 9 for !pq.IsEmpty() { item, _ := pq.Pop() fmt.Println(item) } }
二叉搜索树
二叉搜索树（Binary Search Tree，BST）
1、对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。
注：因为 BST 一般不会存在值重复的节点，所以我们一般不会在 BST 中插入已存在的值 —— BST 相关的性质通常都是「严格比较」。
2、对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。
二叉搜索树并不算复杂，但我觉得它可以算是数据结构领域的半壁江山，直接基于 BST 的数据结构有 AVL 树，红黑树等等，拥有了自平衡性质，可以提供 logN 级别的增删查改效率；还有 B+ 树，线段树等结构都是基于 BST 的思想来设计的。
从做算法题的角度来看 BST，除了它的定义，还有一个重要的性质：BST 的中序遍历结果是有序的（升序）。
LC230. Kth Smallest Element in a BST 二叉搜索树中第K小的元素
https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function kthSmallest(root: TreeNode | null, k: number): number { let i = 0 let v: number const traverse = (root: TreeNode | null) => { if (!root) return; traverse(root.left) i++ if (i === k) { v = root.val return } traverse(root.right) } traverse(root) return v };
LC538. Convert BST to Greater Tree 把二叉搜索树转换为累加树
https://leetcode.com/problems/convert-bst-to-greater-tree/description/
（本题与 LC1038. Binary Search Tree to Greater Sum Tree 相同）
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function convertBST(root: TreeNode | null): TreeNode | null { const traverse = (root: TreeNode | null, base: number) => { if (!root) return base; const sum = traverse(root.right, base) root.val += sum return traverse(root.left, root.val) } traverse(root, 0) return root };
一个更低心智负担的解法：外部维护 sum
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function convertBST(root: TreeNode | null): TreeNode | null { let sum = 0; const traverse = (root: TreeNode | null) => { if (!root) return; traverse(root.right) sum = root.val += sum traverse(root.left) } traverse(root) return root };
LC 98. Validate Binary Search Tree 验证二叉搜索树
https://leetcode.com/problems/validate-binary-search-tree/
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function isValidBST(root: TreeNode | null): boolean { const traverse = (root: TreeNode | null, min: number, max: number): boolean => { if (!root) return true if (root.val >= max || root.val <= min) return false return traverse(root.left, min, root.val) && traverse(root.right, root.val, max) } return traverse(root, -Infinity, Infinity) };
LC 700. Search in a Binary Search Tree 二叉搜索树中的搜索
https://leetcode.com/problems/search-in-a-binary-search-tree/description/
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function searchBST(root: TreeNode | null, val: number): TreeNode | null { if (!root) return null; if (root.val === val) return root; if (val < root.val) { return searchBST(root.left, val) } else { return searchBST(root.right, val) } };
LC 701. Insert into a Binary Search Tree 二叉搜索树中的插入操作
https://leetcode.com/problems/insert-into-a-binary-search-tree/description/
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null { if (!root) return new TreeNode(val); if (val < root.val) { root.left = insertIntoBST(root.left, val) } else { root.right = insertIntoBST(root.right, val) } return root };
LC 450. Delete Node in a BST 删除二叉搜索树中的节点
https://leetcode.com/problems/delete-node-in-a-bst/description/
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function deleteNode(root: TreeNode | null, key: number): TreeNode | null { if (!root) return null; if (root.val === key) { if (!root.left) return root.right; if (!root.right) return root.left; const rightMinNode = getMinNode(root.right) root.right = deleteNode(root.right, rightMinNode.val) rightMinNode.left = root.left rightMinNode.right = root.right root = rightMinNode; } else if (key < root.val) { root.left = deleteNode(root.left, key) } else { root.right = deleteNode(root.right, key) } return root; }; function getMinNode(root: TreeNode): TreeNode { let node = root; while (node.left) { node = node.left; } return node; }