前言

这篇是学习算法课的笔记。这段时间打算整理下最近学习的算法笔记。

数据结构

堆是一颗完全二叉树，最后一层节点从左到右依次排布。堆的插入，更新操作时间复杂度是logn的

堆的存储

用数组存储（完全二叉树都可以用数组来存储）。从索引1开始，左儿子是2x，右儿子是2x+1。

小根堆的性质

每个点是小于等于左右儿子的。小根堆的根是所有数据的最小值。
我们下面的讨论都是根据小根堆这个前提。

小根堆的基本操作和实现

down(x)

当一个值变大了，要做down操作。down操作比较x和左右儿子，然后把最小的值作为父节点，重复交换，直到不能交换为止（x小于等于左右儿子或者x到叶子节点）
再次比较，接着执行down操作。

up(x)

比较x和父节点，最小的up上去。交换到不能交换（x小于父节点或者x到了根节点）

手写一个堆

heap是一个数组，我们用数组来模拟完全二叉树。

插入一个数

heap[++size] = x;  
up(size); 

在最后的位置插入，然后通过up操作调整x的位置。

求集合中的最小值

heap[1]

直接返回树顶元素即可。

删除最小值

heap[1] = heap[size--];
down(1);

把最后一个数覆盖第一个数，size--，然后执行down(1)。因为数组删除头节点很麻烦，所以我们改成删除用尾节点覆盖，然后删除尾节点即可。

删除第k个元素

heap[k] = heap[size--];
down(k);
up(k);

删除后，要判断元素是变大还是变小了，但是我们可以忽略比较。把down和up操作都执行下，因为down和up操作只会执行一个。

修改任意一个元素

heap[k];
down(k);
up(k);

修改第k个元素，然后执行down和up操作。

down操作代码

public void down(int i){
  int k = i;
  if(i * 2 <= heap.length() && heap[i * 2] < h[k] ){
    k = i * 2;
  }

  if(i * 2 + 1 <= heap.length() && heap[i * 2 + 1] < h[k]){
    k = i * 2 + 1;
  }

  if(i != k){
    int temp = heap[k];
    heap[k] = heap[i];
    heap[i] = temp;
    down(k);
  }
}

up操作代码

public void up(int i ){
  while( i / 2 > 0 && heap[i / 2] > heap[i]){
      int temp = heap[i / 2];
      heap[i / 2] = heap[i];
      heap[i] = temp;

      i /= 2;
  }
}

初始化一个堆

// 读入数据
for( int i = 1; i < heap.length(); i++){
  heap[i] = data[i - 1];
}

// 构建堆
for( int i = data.length() / 2 ; i > 0; i-- ){
  down(i);
}

堆和优先队列

堆是优先队列的一种实现方式。

Java的优先队列

Java的优先队列默认是从小到大排序，支持以下方法：

1. 添加元素：offer，add
2. 返回队列头部元素： poll，peek
3. 删除特定元素： remove
4. 支持自定义comparator，可以用来实现从大到小排序