目录
一、二叉树的顺序存储
1.1 存储方式
使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。
一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。这种方式的主要用法就是堆的表示。
1.2 下标关系
- 已知双亲(
parent)的下标，则：
左孩子(left)下标 =2 * parent + 1;
右孩子(right)下标 =2 * parent + 2; - 已知孩子（不区分左右）(
child)下标，则：
双亲(parent)下标 =(child - 1) / 2;
二、堆（Heap）
2.1 堆的相关概念
- 堆逻辑上是一棵完全二叉树；
- 堆物理上是保存在数组中；
- 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆；
- 反之，则是小堆，或者小根堆，或者最小堆；
- 堆的基本作用是：快速找集合中的最值。
2.2 操作-向下调整
前提：左右子树必须已经是一个堆，才能调整。
创建一个大根堆
建堆是自底向上的建堆方式。
以大根堆为例，首先得创建一个大根堆：
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap(){
this.elem = new int[10];
}
/**
* 创建大根堆
* @param array
*/
public void creatHeap(int[] array){
for (int i = 0; i < array.length; i++) {
this.elem[i] = array[i];
usedSize++;
}
//parent代表每颗子树的根节点 ，(array.length - 1)最后一个节点的下标，(array.length - 1 - 1) / 2最后一个节点的根节点
for(int parent= (array.length - 1 - 1) / 2; parent >= 0; parent--)
//第二个参数每次调整的结束位置是不确定的
adjustDown(parent,this.usedSize);
}
测试代码：
public static void main(String[] args) {
int[] arr = {1,5,3,8,7,6};
TestHeap testHeap = new TestHeap();
testHeap.creatHeap(arr);
//在此处打断点调试
System.out.println("dvsfb");
}
输出结果：
// 建堆前
int[] array = { 1,5,3,8,7,6 };
// 建堆后
int[] array = { 8,7,6,5,1,3 };
堆排序中建堆过程时间复杂度为O(n)
时间复杂度详解
自底向上的建堆方式，即 Floyd 建堆算法。因为方向相反、自顶向下的建堆方式的时间复杂度为 O(n·logn)。
假设目标堆是一个满堆，即第 k 层节点数为 2ᵏ。输入数组规模为 n, 堆的高度为 h, 那么 n 与 h 之间满足 n = 2ʰ⁺¹ - 1，可化为 h = log₂(n+1) - 1。 (层数 k 和高度 h 均从 0 开始，即只有根节点的堆高度为0，空堆高度为 -1)。建堆过程中每个节点需要一次下滤操作，交换的次数等于该节点到叶节点的深度。那么每一层中所有节点的交换次数为节点个数乘以叶节点到该节点的深度（如第一层的交换次数为 2⁰ · h，第二层的交换次数为 2¹ · (h-1)，如此类推）。从堆顶到最后一层的交换次数 Sn 进行求和：Sn = 2⁰ · h + 2¹ · (h - 1) + 2² · (h - 2) + ...... + 2ʰ⁻² · 2 + 2ʰ⁻¹ · 1 + 2ʰ · 0；记为①；
①经化简为: Sn = h + 2¹ · (h - 1) + 2² · (h - 2) + ...... + 2ʰ⁻² · 2 + 2ʰ⁻¹；
对①等于号左右两边乘以2，记为②式：
②: 2Sn = 2¹ · h + 2² · (h - 1) + 2³ · (h - 2) + ...... + 2ʰ⁻¹ · 2 + 2ʰ；
用②式减去①式，其中②式的操作数右移一位使指数相同的部分对齐（即错位相减法）：
化简可得③式：
③ : Sn = -h + 2¹ + 2² + 2³ + ...... + 2ʰ⁻¹ + 2ʰ；
对指数部分使用等比数列求和公式：
得：Sn =2ʰ⁺¹ - (h + 2)在上述过程中，已经达到n和h的关系为： h = log₂(n+1) - 1，将其代入Sn中得：Sn =(n+1)(log2(n+1)-1+2)
化简后为：Sn = n - log₂(n + 1)
而对于对数函数，当n趋近于一定值时，其结果相对于x轴趋于平缓，并且变化幅度不大，因此最终可得渐进复杂度为 O(n)。
向下调整的过程
-
parent如果已经是叶子结点，则整个调整过程结束。 - 定义根节点为
parent，则其左孩子节点为：child = 2 * parent+ 1； - 找到左右孩子的最大值，前提是的有右孩子， 因为堆的存储结构是数组，所以判断是否有右孩子即判断右孩子下标是否越界，即
child+ 1< len表明未越界，如果有右孩子并且左孩子比右孩子小，则child++；即右孩子为child； - 确定
parent和child，孩子和父亲的节点大小，如果孩子节点大，则进行交换； - 因为
parent位置的堆的性质可能被破坏，所以把child视作parent，在parent的基础上重新定义child，向下重复以上过程。
代码示例：
public void adjustDown(int root,int len){
int parent = root;
int child = 2 * parent+ 1;//左孩子
while(child < len){
//找到左右孩子的最大值，前提是的有右孩子
//如果有右孩子并且左孩子比右孩子小，则child++
if(child + 1 < len && elem[child] < elem[child + 1]){
child++;
}
//判断孩子和父亲的节点大小，如果孩子节点大，则进行交换
if(elem[child] > elem[parent]){
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2* parent +1;
}else{
//当调整过程中，已经没有可以继续再进行调整的节点了，直接break结束
break;
}
}
}
三、堆的应用（优先级队列）
数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。利用堆来构建优先级队列。
3.1入队列
入队列过程（以大堆为例）：
- 首先按尾插方式放入数组；
- 比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束；
- 否则，交换其和双亲位置的值，重新进行 2、3 步骤；
- 直到根结点。
代码示例：
/**
* 入堆 向上调整
* @param child
*/
public void adjustUp(int child){
int parent = (child - 1) / 2;
while (child > 0){
if(this.elem[child] > this.elem[parent]){
int tmp = this.elem[child];
this.elem[child] = this.elem[parent];
this.elem[parent] = tmp;
child = parent;
parent = (child - 1) / 2;
}else {
break;
}
}
}
public void push(int val){
if(isFull()){
this.elem = Arrays.copyOf(this.elem,this.elem.length * 2);
}
this.elem[this.usedSize] = val;//10
usedSize++;//11
adjustUp(this.usedSize - 1);//10
}
//判断是否满了
public boolean isFull(){
return this.usedSize == this.elem.length;
}
3.2 操作-出队列（优先级最高）
为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向下调整方式重新调整成堆。
public void pop(){
if(isEmpty()){
return;
}
//让0下标的元素和最后一个元素进行交换
int tmp = this.elem[0];
this.elem[0] = this.elem[usedSize - 1];
this.elem[usedSize - 1] = tmp;
usedSize--;
//向下调整
adjustDown(0,usedSize);
}
//判断是否为空
public boolean isEmpty(){
return this.usedSize == 0;
}
3.3 返回队首元素（优先级最高）
返回堆顶元素即可。
//返回队首元素
public int peek(){
if(isEmpty()){
return -1;
}
//得到队头元素
return this.elem[0];
}
3.4 堆排序
- 先创建大堆，调整每棵树；
- 开始堆排序，先交换，再向下调整，直到end为0。
//堆排序
//先创建大堆，调整每棵树
//开始堆排序，先交换，再调整，直到end为0
public void heapSort(){
int end = this.usedSize - 1;
while (end > 0){
int tmp = this.elem[0];
this.elem[0] = this.elem[end];
this.elem[end] = tmp;
adjustDown(0,end);
end--;
}
}
四、对象的比较
4.1 equals
equal只能按照相等进行比较，不能按照大于、小于的方式进行比较.
public static void main(String[] args) {
Student student1 = new Student("zhang",12);
Student student2 = new Student("li",89);
System.out.println(student1.equals(student2));//false 重写equals方法，如果不重写则默认调用的是Object的equals方法
}
4.2 Comparble
对于用户自定义的类型，如果要想按照大小的方式进行比较时：在定义类时，实现Comparble接口即可，然后在类中重写compareTo方法。Compareble是java.lang中的接口类，可以直接使用。
class Student implements Comparable<Student>{
public String name;
public int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
//重写compareTo方法
public int compareTo(Student o) {
return this.age - o.age;
}
}
4.3 Comparator
需覆写Comparator中的compare方法；Comparator是java.util 包中的泛型接口类，使用时必须导入对应的包。
class Student{
public String name;
public int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return age == student.age &&
Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}
class AgeComparator implements Comparator<Student> {
@Override
//compare的第一个参数是插入的元素
public int compare(Student o1, Student o2) {
return o1.getAge() - o2.getAge();//默认小堆
//return o2.getAge() - o1.getAge();//大堆
}
}
class NameComparator implements Comparator<Student>{
@Override
public int compare(Student o1, Student o2) {
return o1.getName().compareTo(o2.getName());
}
}
测试代码：
public static void main(String[] args) {
Student[] students = new Student[2];
students[0] = new Student("ang",102);
students[1] = new Student("za",92);
//按照年龄排序
Arrays.sort(students, new AgeComparator());
//按照名字首字母排序
// Arrays.sort(students, new NameComparator());
System.out.println(Arrays.toString(students));
}
输出结果：
4.4 三种方法的比较
| 覆写的方法 | 说明 |
|---|---|
| Object.equals | 因为所有类都是继承自 Object 的，所以直接覆写即可，不过只能比较相等与否 |
| Comparable.compareTo | 需要手动实现接口，侵入性比较强，但一旦实现，每次用该类都有顺序，属于内部顺序 |
| Comparator.compare | 需要实现一个比较器对象，对待比较类的侵入性弱，但对算法代码实现侵入性强 |
五、PriorityQueue 的比较方式
集合框架中的PriorityQueue底层使用堆结构，因此其内部的元素必须要能够比大小，PriorityQueue采用了：Comparble和Comparator两种方式。
-
Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法。 - 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现
Comparator接口并覆写compare方法。
public static void main(String[] args) {
//堆默认大小是10
PriorityQueue<Integer> queue = new PriorityQueue<>();
//默认是小堆排序
queue.offer(61);
queue.offer(21);
queue.offer(1);
System.out.println(queue);//[1, 61, 21]
}
从输出队列可看出其优先级队列默认为小堆排序。
结合4.3方法 PriorityQueue的比较结果：
public static void main(String[] args) {
//按照名字首字母进行比较
// PriorityQueue<Student> priorityQueue = new PriorityQueue<>(new NameComparator());
//按照年龄比较
PriorityQueue<Student> priorityQueue = new PriorityQueue<>(new AgeComparator());
priorityQueue.offer(new Student("ang",12));
priorityQueue.offer(new Student("li",4));
System.out.println(priorityQueue);
}
输出结果：
六、TopK问题
TopK问题
在一个数组中找出最大的K个或者最小的K个。
若想找出最大的k个，先用前k个元素生成一个小顶堆，这个小顶堆用于存储，当前最大的k个元素。接着，从第k+1个元素开始扫描，和堆顶（堆中最小的元素）比较，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。直到，扫描完所有n-k个元素，最终堆中的k个元素，就是所求的TopK。
代码示例：
找出前三个最大的元素：
public static void TopK(int arr[],int k){
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// return o2 - o1;//大堆
return o1 - o2;//小堆
}
});
for (int i = 0; i < arr.length; i++) {
//先向队列中放入前k个元素
if (maxHeap.size() < k){
maxHeap.offer(arr[i]);
}else {
int top = maxHeap.peek();
// if (top > arr[i]){ //找出前三个最小的
if (top < arr[i]){ //找出前三个最大的
maxHeap.poll();
maxHeap.offer(arr[i]);
}
}
}
System.out.println(maxHeap);
}
public static void main(String[] args) {
//找到前三个最小的数
//建立大小为3的大堆
int[] arr = {1,31,2,10,7,35,21,19,56};
TopK(arr,3);
}
输出结果：
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> o1, List<Integer> o2) {
return (o2.get(0) + o2.get(1) - (o1.get(0) + o1.get(1)));//大堆
}
});
for (int i = 0; i <nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
if(maxHeap.size() < k){
List<Integer> pair = new ArrayList<>();
pair.add(nums1[i]);
pair.add(nums2[j]);
maxHeap.offer(pair);
}else {
List<Integer> top = maxHeap.peek();
//如果当前元素比堆顶小，就弹出堆顶，然后将小的数据入堆
int topValue = top.get(0)+top.get(1);
if (topValue > nums1[i] +nums2[j]){
maxHeap.poll();
List<Integer> pair = new ArrayList<>();
pair.add(nums1[i]);
pair.add(nums2[j]);
maxHeap.offer(pair);
}
}
}
}
//堆当中放的就是最后的结果
List<List<Integer>> ret = new ArrayList<>();
for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {
ret.add(maxHeap.poll());
}
return ret;
}
以上。