二、堆
1. 什么是堆？
堆其实也是一种基于树实现的数据结构。基于二叉树实现的堆叫做二叉堆。
2. 二叉堆：
上面说了基于二叉树实现的堆叫二叉堆，有如下特点：
- 二叉堆是一棵完全二叉树。
- 所有节点的父节点的值都比自己大。
我们可以使用数组来存储二叉堆，如下图。
左孩子的索引就等于父节点索引的两倍再加1，右孩子索引就是父节点索引的两倍再加2。
3. 堆的实现：
根据上面的分析，写出堆的基本结构。
public class MaxHeap<E extends Comparable<E>> { private Array<E> data;//存储数据的动态数组 public MaxHeap(int capacity){ data = new Array<>(capacity); } public MaxHeap(){ data = new Array<>(); } /** 返回堆中元素个数 */ public int size(){ return data.getSize(); } /** 判断堆是否为空 */ public boolean isEmpty(){ return data.isEmpty(); } /** 计算指定索引节点的父节点的索引 */ private int parent(int index){ if (index == 0) throw new IllegalArgumentException("最顶层节点无父节点"); return (index -1) / 2; } /** 计算指定索引的左孩子的索引 */ private int leftChild(int index){ return index * 2 + 1; } /** 计算指定索引的右孩子的索引 */ private int rightChild(int index){ return index * 2 + 2; } }
这里还是使用到了前一篇文章中自己实现的动态数组。接下来看看对堆的一些操作。
- 向堆中添加元素：
添加元素直接使用动态数组的addLast方法把元素添加到最后即可，但是还要看看添加后是否还满足二叉堆的性质，看看自己是不是比自己父节点更小。如果比自己父节点更大，就需要上浮，也就是自己和父节点交换位置。那么先在动态数组添加一个交换连个元素位置的方法：
/** 交换两个元素的位置 */ public void swap(int x,int y){ if (x<0 || x>=size || y<0 || y>=size ) throw new IllegalArgumentException("传入的索引不合法"); E temp = data[x]; data[x] = data[y]; data[y] = temp; }
接下来就可以执行添加操作：
/** 向堆中添加元素 */ public void add(E e){ data.addLast(e); siftUp(data.getSize() - 1); } /** 若添加的元素比父节点元素更大，就不符合完全二叉树性质，需要上浮。 * 所谓上浮就是该元素和父节点元素交换位置。 */ private void siftUp(int k){ while (k>0 && data.get(parent(k)).compareTo(data.get(k)) < 0){ data.swap(k,parent(k)); k = parent(k); }
- 删除元素：
限定只能从根节点取出元素，所以取出的元素也是最大的，因此也叫最大堆。但是删除了根节点，这棵树就变成两棵子树了，我们就把最后一个元素放到根节点的位置，让它成为根节点。但是为了满足完全二叉树的性质，就要判断这个新的根节点是否比自己的孩子更大，如果不是，就需要下沉。下沉的时候就跟它的左右孩子中较大的那个交换位置即可。
/** 查看堆中最大元素 */ public E findMax(){ if (data.getSize() == 0) throw new IllegalArgumentException("堆为空"); return data.get(0); } /** 取出堆中最大元素 */ public E extractMax(){ E temp = findMax(); data.swap(0,data.getSize() - 1); data.removeLast(); siftDown(0); return temp; } /** 下沉操作 */ private void siftDown(int k){ while (leftChild(k) < data.getSize()){ int j = leftChild(k);//左孩子索引 //k节点的右孩子比左孩子大 if (j+1 < data.getSize() && data.get(j+1).compareTo(data.get(j)) > 0){ j = rightChild(k);// } if (data.get(k).compareTo(data.get(j)) >= 0) break; data.swap(k,j); k = j; } }
在上图添加元素的基础上删除62，就变成了这样：
- 取出堆中最大元素后放入一个新的元素：
/** 将最大元素替换成新元素 */ public E replace(E e){ E temp = findMax(); data.update(0,e); siftDown(0); return temp; }
这个操作比较简单，直接将索引为0处的元素更新，然后再下沉即可。
- 将任意数组整理成堆的形状(heapify)：
找到最后一个非叶子节点，从它开始做下沉操作。最后一个元素的索引的父节点索引就是最后一个非叶子节点的索引。
比如在此图中，最后一个非叶子节点是“22”，那么就是利用“62”的索引去计算“22”的索引。“22”的索引为4，那么需要做下沉操作的就是索引为4、3、2、1、0的这5个元素。上图做完下沉操作后变成：
下面看代码实现。首先在上篇文章讲的动态数组中添加一个构造函数，即传入一个数组的构造函数。
public Array(E[] arr){ data = (E[]) new Object[arr.length]; for (int i=0;i<arr.length;i++){ data[i] = arr[i]; size = arr.length; } }
然后heapify操作也写成一个构造函数。
/** heapify */ public MaxHeap(E[] arr){ data = new Array<>(arr); for (int i=parent(arr.length-1);i>=0;i--){ siftDown(i); } }
这样就完成了heapify操作。
三、优先队列
1. 什么是优先队列？
前面讲到了队列，特点是先进先出，优先队列就是出队顺序跟入队顺序无关，与元素的优先级相关。计算机可以同时执行多任务，它在给这些应用分配内存时，其实就是使用优先队列，优先级高的任务优先使用内存，以保证带给用户最好的体验。
2. 优先队列的实现：
有了上面实现的最大堆，实现优先队列就非常简单了。因为最大堆的根节点就是优先级最高的元素，每次从最大堆中取出的也就是根节点。所以使用最大堆来实现优先队列，直接调用最大堆对应的方法就行了。
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> { private MaxHeap<E> maxHeap; public PriorityQueue(){ maxHeap = new MaxHeap<>(); } @Override public int getSize() { return maxHeap.size(); } @Override public boolean isEmpty() { return maxHeap.isEmpty(); } @Override public void enqueue(E e) { maxHeap.add(e); } @Override public E dequeue() { return maxHeap.extractMax(); } @Override public E getFront() { return maxHeap.findMax(); } }
其实Java也给我们提供了一个优先队列，在java.util包中有一个PriorityQueue，就是优先队列。这个PriorityQueue是一个最小堆，也就是说，每次取出是优先级最小的元素。还有就是一些方法名不同，比如入队操作是add。更多的不同请在使用过程中体会。
四、哈希表
1. 什么是哈希表？
所谓哈希表，就是将我们关心的key通过哈希函数转化成数组对应的索引，从而可以直接通过索引访问到元素。
2. 哈希函数的设计：
- 整形：
小范围的整形key可以直接当作索引。若有负数，就进行偏移。若是大整数，比如身份证号，可以进行取模(模一个素数)，所谓取模就是求余。有一个网站给出了对于指定范围内的数到底对多少取模更合适，给出该网站的网址：
https://planetmath.org/goodhashtableprimes
- 字符串：
可以自己定义一些转换规则，将字符串转成整形来处理。
- 引用类型：
依然可以通过自己指定的转换规则转换为整形来处理。
设计函数要遵循以下三个原则：
- 一致性：如果 a == b，则 hash(a) == hash(b)。
- 高效性：计算哈希函数高效简便。
- 均匀性：哈希值均匀分布。
3. Java提供的hashCode方法：
Java的Object类中有一个hashCode方法，这个方法是根据对象在内存中地址值来计算哈希值的。基本类型需要使用其对应的包装类调用，引用类型可直接调用，也可以重写该方法，根据自己定义的规则来计算哈希值。java中HashSet和HashMap集合底层使用的就是哈希表。
4. 解决哈希冲突：
所谓哈希冲突，就是通过不同的对象通过哈希函数计算出来的哈希值可能是一样的。但是我们需要使用哈希值充当数组索引，那就不能有重复的哈希值。解决办法就是，数组每个索引位置存储的不是某一个元素，而是一个链表或者是一棵红黑树。java8中就是这样解决哈希冲突的，首先是存储链表，当哈希冲突达到一定程度时，就存储红黑树。
总结：
本文主要介绍了树、堆以及优先队列。树主要说了二分搜索树，要理解二分搜索树的操作，就要理解递归。后面说的堆其实也就是一棵树，这里说的是基于二叉树实现的最大堆。而后面说的优先队列，又是基于堆来实现的。包括《数据结构01》的源码，点此即可下载。
