在计算机的世界里，优先级队列是个非常实用的工具，它能根据元素的优先级来处理任务。而左偏堆和斜堆就是实现高效优先级队列的两种数据结构。下面咱们就来详细聊聊这两种数据结构。
一、什么是优先级队列
在生活中，我们去银行办理业务，会有 VIP 客户优先办理，这其实就是一种优先级的体现。在计算机里，优先级队列也是类似的，它会根据元素的优先级来决定处理顺序，优先级高的元素会先被处理。
比如说，在一个任务调度系统中，有一些紧急任务和普通任务，紧急任务的优先级高，就会先被处理。这就是优先级队列的应用场景。
二、左偏堆的介绍
1. 左偏堆的概念
左偏堆是一种二叉树结构，它有个特点，就是左子树的路径比右子树的路径长。左偏堆的节点除了保存元素值，还保存一个距离值，这个距离值表示从该节点到最近的外部节点的距离。
2. 左偏堆的操作
左偏堆主要有插入、删除和合并操作。
插入操作
插入操作其实就是把新元素当作一个只有一个节点的左偏堆，然后和原来的左偏堆进行合并。
以下是用 Java 实现的左偏堆插入操作示例：
// Java 技术栈
// 定义左偏堆节点类
class LeftistNode {
int value;
int dist;
LeftistNode left;
LeftistNode right;
public LeftistNode(int value) {
this.value = value;
this.dist = 0;
this.left = null;
this.right = null;
}
}
// 定义左偏堆类
class LeftistHeap {
private LeftistNode root;
public LeftistHeap() {
this.root = null;
}
// 合并两个左偏堆
private LeftistNode merge(LeftistNode h1, LeftistNode h2) {
if (h1 == null) {
return h2;
}
if (h2 == null) {
return h1;
}
if (h1.value > h2.value) {
LeftistNode temp = h1;
h1 = h2;
h2 = temp;
}
h1.right = merge(h1.right, h2);
if (h1.left == null || h1.left.dist < h1.right.dist) {
LeftistNode temp = h1.left;
h1.left = h1.right;
h1.right = temp;
}
if (h1.right == null) {
h1.dist = 0;
} else {
h1.dist = h1.right.dist + 1;
}
return h1;
}
// 插入操作
public void insert(int value) {
LeftistNode newNode = new LeftistNode(value);
root = merge(root, newNode);
}
}
删除操作
删除操作就是删除根节点，然后把根节点的左右子树合并。
以下是 Java 实现的左偏堆删除操作示例：
// Java 技术栈
// 继续使用上面定义的 LeftistNode 和 LeftistHeap 类
// 在 LeftistHeap 类中添加删除操作方法
public int deleteMin() {
if (root == null) {
throw new RuntimeException("Heap is empty");
}
int minValue = root.value;
root = merge(root.left, root.right);
return minValue;
}
合并操作
合并操作就是把两个左偏堆合并成一个。上面的代码中已经有合并操作的实现。
3. 左偏堆的优缺点
优点：左偏堆的合并操作时间复杂度是 O(log n)，插入和删除操作也能在 O(log n) 时间内完成，效率比较高。 缺点：左偏堆的实现相对复杂，需要维护节点的距离值。
4. 左偏堆的应用场景
左偏堆适用于需要频繁进行合并操作的场景，比如在任务调度系统中，当有新的任务队列需要和原来的任务队列合并时，左偏堆就很有用。
三、斜堆的介绍
1. 斜堆的概念
斜堆也是一种二叉树结构，它和左偏堆很相似，但是斜堆不需要维护节点的距离值。斜堆在合并操作时，总是交换左右子树。
2. 斜堆的操作
斜堆的操作同样有插入、删除和合并操作。
插入操作
插入操作和左偏堆类似，把新元素当作一个只有一个节点的斜堆，然后和原来的斜堆进行合并。
以下是 Java 实现的斜堆插入操作示例：
// Java 技术栈
// 定义斜堆节点类
class SkewNode {
int value;
SkewNode left;
SkewNode right;
public SkewNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// 定义斜堆类
class SkewHeap {
private SkewNode root;
public SkewHeap() {
this.root = null;
}
// 合并两个斜堆
private SkewNode merge(SkewNode h1, SkewNode h2) {
if (h1 == null) {
return h2;
}
if (h2 == null) {
return h1;
}
if (h1.value > h2.value) {
SkewNode temp = h1;
h1 = h2;
h2 = temp;
}
SkewNode temp = h1.right;
h1.right = h1.left;
h1.left = merge(temp, h2);
return h1;
}
// 插入操作
public void insert(int value) {
SkewNode newNode = new SkewNode(value);
root = merge(root, newNode);
}
}
删除操作
删除操作就是删除根节点，然后把根节点的左右子树合并。
以下是 Java 实现的斜堆删除操作示例：
// Java 技术栈
// 继续使用上面定义的 SkewNode 和 SkewHeap 类
// 在 SkewHeap 类中添加删除操作方法
public int deleteMin() {
if (root == null) {
throw new RuntimeException("Heap is empty");
}
int minValue = root.value;
root = merge(root.left, root.right);
return minValue;
}
合并操作
合并操作就是把两个斜堆合并成一个。上面的代码中已经有合并操作的实现。
3. 斜堆的优缺点
优点：斜堆的实现相对简单，不需要维护节点的距离值，而且合并操作的平均时间复杂度也是 O(log n)。 缺点：斜堆的最坏时间复杂度可能达到 O(n)，不过这种情况比较少见。
4. 斜堆的应用场景
斜堆适用于对实现复杂度有要求，同时对性能要求不是特别高的场景，比如一些简单的任务调度系统。
四、左偏堆和斜堆的比较
1. 实现复杂度
左偏堆需要维护节点的距离值，实现相对复杂；斜堆不需要维护距离值，实现相对简单。
2. 性能
左偏堆的时间复杂度比较稳定，插入、删除和合并操作的时间复杂度都是 O(log n)；斜堆的平均时间复杂度也是 O(log n)，但最坏时间复杂度可能达到 O(n)。
3. 应用场景
如果需要频繁进行合并操作，并且对性能要求较高，左偏堆是更好的选择；如果对实现复杂度有要求，同时对性能要求不是特别高，斜堆更合适。
五、注意事项
1. 左偏堆的注意事项
在实现左偏堆时，要注意维护节点的距离值，确保距离值的正确性，否则可能会影响合并操作的性能。
2. 斜堆的注意事项
虽然斜堆的最坏时间复杂度可能达到 O(n)，但在实际应用中，这种情况比较少见。不过在对性能要求极高的场景下，还是要谨慎使用。
六、文章总结
左偏堆和斜堆都是实现高效优先级队列的好方法。左偏堆通过维护节点的距离值，保证了操作的时间复杂度稳定在 O(log n)，适用于对性能要求较高的场景；斜堆实现简单，不需要维护距离值，平均时间复杂度也是 O(log n)，适用于对实现复杂度有要求的场景。在实际应用中，要根据具体的需求来选择合适的数据结构。
评论