2018-11-04 20:03:42
一、优先队列和堆
1、优先队列
能够完成以下操作的数据结构叫做优先队列。
- 插入一个数值
- 取出最小的数值（获得数值并删除）
能够使用二叉树来高效的完成上述的问题的，是一种叫做“堆”的数据结构。
2、堆的结构
堆就是像下图这样的二叉树。
堆的重要性质就是儿子的值一定不能小于父亲的值。除此之外，树的节点是按照从上到下、从左到右的顺序紧凑排列的。
也就是说堆的结构一定是一个完全二叉树，这就给建立堆带来了方便，我们可以直接使用数组来模拟树形结构，并且由于堆是完全二叉树，所以数组里理论上是不会产生浪费的。
3、堆的操作
1）插入：在向堆中插入一个数值的时候，首先在堆的末尾插入一个数值，然后只需要不断的向上提升直到没有大小颠倒为止。
2）获取最小值：首先把堆的最后一个节点的数值复制到根节点，并且删除最后一个节点。然后不断向下交换直到没有大小颠倒为止。在向下交换的过程中，如果有2个儿子，那么选择数值较小的儿子进行交换。
显然这两个操作的时间复杂度都是O(logn)。
4、堆的实现
下面我们看一下堆的实现的例子。正如之前提到的堆的实现可以直接使用数组来保存数据。
- 左儿子的编号是自己编号 * 2 + 1
- 右儿子的编号是自己编号 * 2 + 2
public class Heap {
int[] heap;
int size;
public Heap() {
this.heap = new int[100];
this.size = 0;
}
public void push(int num) {
// 获得自己的idx，同时将size + 1
int idx = size++;
while (idx > 0) {
int parent = (idx - 1) / 2;
if (heap[parent] > num) {
heap[idx] = heap[parent];
idx = parent;
}
else break;
}
heap[idx] = num;
}
public int pop() {
int res = heap[0];
int num = heap[--size];
int idx = 0;
while (idx * 2 + 1 < size) {
int l = idx * 2 + 1;
int r = idx * 2 + 2;
if (r < size && heap[r] < heap[l]) l = r;
if (heap[l] >= num) break;
else {
heap[idx] = heap[l];
idx = l;
}
}
heap[idx] = num;
return res;
}
}
5、编程语言的标准库
实际上，大部分情况下我们都是没有必要自己去实现一个堆的，因为在很多的编程语言中已经实现了堆这个数据结构，Java中可以使用PriorityQueue来实现优先队列的操作。需要注意的是，Java中的PriorityQueue也是一个小顶堆。
6、使用优先队列的题目
- Expedition （POJ 2431）
问题描述：
你需要驾驶一辆卡车行驶L单位的距离。最开始的时候，卡车上有p单位的汽油。卡车每开1单位距离需要消耗1单位的汽油。如果在途中卡车的汽油消耗殆尽，卡车就无法继续前进，因而无法到达终点。在途中有N个加油站。第i个加油站在距离起点Ai单位距离的地方，最多可以给卡车加Bi单位的汽油。假设卡车的燃料箱的容量是无限大的，无论加多少汽油都没有问题。那么请问卡车是否可以达到终点？如果可以到达终点输出最少的加油次数，否则输出-1。
限制条件：
1 <= N <= 10000
1 <= L <= 1000000, 1 <= P <= 1000000
1 <= Ai < L, 1 <= Bi <= 100
问题求解：
本题是一个较为经典的使用优先队列求解的问题，解题思路就是每次经过一个站点可以先不加油，将当前可加的油量放入一个优先队列中，在后续行进过程中如果发生了油量不够的情况，这个时候可以将优先队列中油量最大的数值取出依次加到油箱中，如果所有的油都已经加入，但是依然不能继续前往下一个加油点，那么就可以直接返回-1。
import java.util.*;
public class Expedition {
public static int helper(int P, List<Stop> stops) {
int res = 0;
int pos = 0;
int oil = P;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i = 0; i < stops.size(); i++) {
int dis = stops.get(i).pos - pos;
while (oil < dis) {
if (pq.isEmpty()) return -1;
oil += -pq.poll();
res++;
}
oil -= dis;
pos = stops.get(i).pos;
pq.add(-stops.get(i).oil);
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
List<Stop> stops = new ArrayList<Stop>();
for (int i = N - 1; i >= 0; i--) {
int pos = sc.nextInt();
int oil = sc.nextInt();
Stop stop = new Stop(pos, oil);
stops.add(stop);
}
int pos = sc.nextInt();
stops.add(new Stop(pos, 0));
for (int i = 0; i < N; i++) {
Stop cur = stops.get(i);
cur.pos = pos - cur.pos;
}
int P = sc.nextInt();
Collections.sort(stops, new Comparator<Stop>() {
@Override
public int compare(Stop o1, Stop o2) {
return o1.pos - o2.pos;
}
});
System.out.println(helper(P, stops));
}
}
class Stop {
public int pos;
public int oil;
public Stop(int pos, int oil) {
this.pos = pos;
this.oil = oil;
}
}
- Fence Rapair （POJ 3253）
问题描述：
农夫为了修理栅栏，需要将一块很长的木板切割成N块。准备切成的木板的长度为L1，L2，...，LN，未切割前木板的长度恰好为切割后木板长度的总和。每次切断木板时，需要的开销为这块木板的长度。例如长度为21的木板切成5，8，8三块。长度21的木板切成13和8的时候，开销为21。再将长度为13的木板切割成5，8的时候，开销为13。因此总的开销为34。请求出按照目标要求将木板切割完最小的开销是多少。
问题求解：
首先切割的方法可以是用二叉树来形象的表示，二叉树中每一个叶子节点就对应了切割出的一块木板。叶子节点的深度就对应了为了得到该木板需要的切割次数，开销的合计就是各个叶子节点的木板长度 * 节点深度。
之前贪心算法中讲到过朴素的解法的时间复杂度为O(n ^ 2)，下面我们重新再来看这个问题，每次都要取出最小的两个元素，不正符合优先队列的含义么？因此，这条题目本质是使用优先队列进行求解，可以在O(nlogn)的时间复杂度内完成求解。
import java.util.PriorityQueue;
import java.util.Scanner;
public class FencerRepair {
private static long helper(int[] nums) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i : nums) pq.add(i);
long res = 0;
while (pq.size() > 1) {
int x = pq.poll();
int y = pq.poll();
int tmp = x + y;
res += tmp;
pq.add(tmp);
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
System.out.println(helper(nums));
}
}
二、二叉搜索树
1、二叉搜索树的结构
二叉搜索树是能够高效的进行如下操作的数据结构。
1）插入某个数值
2）查询是否包含某个数值
3）删除某个数值
根据实现的不同，还可以实现其他各种各样的操作，是一种实用性很高的数据结构。二叉搜索树的结构需要满足的性质是：二叉搜索树的所有节点都满足左子树上的所有节点都比自己小，右子树上的所有节点都比自己大。
2、二叉搜索树的操作
1）查询：从根节点开始查询，如果和目标值相等直接返回true，如果大于当前节点，则递归的查询其右子树，否则递归的查询其左子树。
2）插入：插入操作其实和查询非常的类似，首先要做的就是查询到当前的数值应该插入的位置，然后进行插入即可。
3）删除：删除操作相对于其他两个操作来说是要稍微复杂一点的，需要根据以下几种情况来分别讨论处理。
1‘ 需要删除的节点没有左儿子，那么就需要把右儿子给提上去
2’ 需要删除的节点的左儿子没有右儿子，那么就把左儿子给提上去
3‘ 以上两种情况都不满足的话，就把左儿子的子孙中最大的节点提到需要删除的节点上
以上的三个操作都是和树高成正比，那么平均的时间复杂度就是O(logn)。
3、二叉搜索树的实现
public class BST {
private TreeNode root;
public boolean find(int num) {
return find(root, num);
}
private boolean find(TreeNode root, int num) {
if (root == null) return false;
if (root.val > num) return find(root.left, num);
else if (root.val < num) return find(root.right, num);
else return true;
}
public void insert(int num) {
root = insert(root, num);
}
private TreeNode insert(TreeNode root, int num) {
if (root == null) {
TreeNode node = new TreeNode(num);
return node;
}
else if (root.val > num) root.left = insert(root.left, num);
else if (root.val < num) root.right = insert(root.right, num);
return root;
}
public void delete(int num) {
root = delete(root, num);
}
private TreeNode delete(TreeNode root, int num) {
if (root == null) return null;
else if (root.val < num) root.right = delete(root.right, num);
else if (root.val > num) root.left = delete(root.left, num);
else if (root.left == null) return root.right;
else if (root.left.right == null) {
root.left.right = root.right;
return root.left;
}
else {
TreeNode cur = root.left;
while (cur.right != null) cur = cur.right;
root.val = cur.val;
root.left = delete(root.left, root.val);
}
return root;
}
}
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}