优先队列和堆排

优先队列

定义：可以移除最大或最小的元素。

API：插入，删除，是否为空，大小

应用：数值计算，数据压缩，图搜索，人工智能，统计学，操作系统，离散优化，垃圾过滤

初级实现：数组实现(无序)，数组实现(有序)，链表实现。

二叉堆

数组实现，实际上并没有显式的连接。

堆有序：当一棵二叉树的每个节点都大于等于它的两个子节点时，它被称为堆有序。
根节点是堆有序的二叉树中的最大节点。
二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级存储(不使用数组的第一个位置)
主要API在于：swim(),sink();

快速排序

quicksort

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Quick{
    public class void sort(Comparable[] a){
        StdRandom.shuffle(a);
        sort(a,0,a.length - 1);
    }

    private static void sort(Comparable[] a,int lo,int hi){
        if(hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a,j + 1, hi);
    }
}

归并排序

• Divide array into two halves.
• Recursively sort each other.
• Merge two halves.

原地归并

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

private static void merge(Comparable[] a,Comparable[] aux,int lo,int mid,int hi){
    assert isSorted(a,lo,mid); //precondition
    assert isSorted(a,mid+1,hi); //precondition

    for(int k=lo;k<=hi;k++){
        aux[k] = a[k];   //copy
    }

    //merge back to a[]
    int i = lo; j = mid + 1;
    for(int k=lo;k<=hi;k++){
        if(i > mid)               a[k] = aux[j++];
        else if(j > hi)           a[k] = aux[i++];
        else if(less(a[j],a[i]))  a[k] = aux[j++];
        else                      a[k] = aux[i++];
    }

    assert isSort(a,lo,hi);
}

Sort

Introduction

• Goal.Sort any type of data.

How can sort() konw how to compare data of type Double,String,and java.io.File without any information about the type of an item’s key?

Stack

Implement

• use Linkedlist
• use Array

Tradeoffs: Array VS Linkedlist

• Linkedlist
  • Every operation takes constant time in the worst case.
  • Uses extra time and space to deal with links.

动态连接 并查集

• Union command 连接两个物体

• 网络，社交网络，

实现查找和合并

1
2
3
4
5
6
7

public class UF{
    UF(int N) // 初始化并查集

    void union(int p,int q) //在p和q之间添加分量

    boolean connected(int p, int q) //p和q之间连通吗？
}

  最近也开学一周了，学校里议论纷纷的是计算机学院研究生跳楼的事，开学第一天，从西十二五楼一跃而下，走前写满了对这个世界的控诉。这真的是多方面的因素造成的，有内心的敏感脆弱，不能和家人朋友的及时沟通，对研究生生活的误解等等。世界上没有真正地感同身受，我不能体会到他跳楼时的绝望。庆幸的是，在我伤心难过的时候，我身边总有人会来安慰我。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.