什么是堆

堆是一种特殊的树，它满足以下两点：

• 堆是一个完全二叉树

  完全二叉树要求，除最后一层，其他层的节点个数都是满的，最后一次的节点都靠左排列。

• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值

  当前节点的值是子树中的最大或最小值。

我们将每个节点的值都大于等于子树中每个节点值的堆，叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”

我们来看一下例子：

在上面的四个实例中，我们根据以上两条规则，可以判断出：

第一个、第二个是大顶堆，第三个是小顶堆，第四个由于不是完全二叉树所以不是堆。

二分查找

前置要求：数组有序

时间复杂度：log(n)

几种常见的问题：

1. 数组中查找target
2. 数组中有重复，查找第一个target
3. 数组中有重复，查找最后一个target
4. 查找等于target或第一个小于target的值
5. 查找等于target或第一个大于target的值

• 冒泡排序
• 插入排序
• 选择排序
• 归并排序
• 快速排序
• 桶排序
• 基数排序
• 计数排序

什么是LRU算法

Least Recently Used，最近最少使用，当数据超过容量时，淘汰最近最少使用的一个然后再进行添加。

用单链表来进行实现：

维护一个链表，从头插入数据。当新数据插入时将新数据作为头部，指向旧的头结点。

向一个单链表插入数据，首先遍历这个链表，查看数据是否已经存在于链表中。如果存在，则删除原有数据，将新数据插入到头结点。

如果不存在，先看是否已经到达容量，如果没有到达容量则插入到头结点。如果到达容量则删除尾部节点，再进行插入。

在这个过程中，将最近使用过的又重新插入到了头部，在链表尾部的就是最近最少使用的一项，所以从尾部删除。

定义树节点的实体类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

private static final boolean RED = true;
private static final boolean BLACK = false;

/**
	 * 红黑树的节点结构
	 * 保存的值，左节点，右节点以及颜色(true为红色，false为黑色)
	 * 默认添加一个红节点
	 *
	 * @param <E>
	 */
static final class RedBlackTreeNode<E extends Comparable<E>> {

  E val;
  RedBlackTreeNode<E> left;
  RedBlackTreeNode<E> right;
  boolean color = RED;


  RedBlackTreeNode(E val) {
    this.val = val;
  }

}

这里简单的定义了一下红黑树，并且只有节点，并不是map这样的k-v结构。如果定义k-v结构到时比较的时候比较k即可。

用了泛型，并且要支持比较(继承自Comparable)，不然无法比较大小进行插入。

然后定义了一个值，左节点和右节点，然后颜色默认为红色。

再增加一个构造函数即可