Make magic out of simple things.
在平凡中创造奇迹。 基础知识通常情况下我们把堆看成是一棵完全二叉树。堆一般分为两种,一种是最大堆,一种是最小堆。最大堆要求根节点的值即大于左子树的值,又大于右子树的值。也就是说最大堆根节点的值是堆中最大的。最小堆根节点的值是堆中最小的,前面我们讲堆排序的时候介绍过堆,实际上他就是数组结构,但因为数组中间有关联,所以我们可以把它当做一棵完全二叉树来看,下面我们再来看一下堆的数据结构是什么样的。
结点中的数字是数组元素的下标,不是数组元素的值。所以如果我们知道父节点的下标我们就可以知道他的两个子节点(如果有子节点),如果知道子节点的下标也一定能找到父节点的下标,他们的关系是:
父节点的下标=(子节点下标-1)>>1;
左子节点下标=父节点下标*2+1;
右子节点下标=父节点下标*2+2;
堆的创建:堆有两种,一种是最大堆,一种是最小堆。顾名思义,最大堆就是堆顶的元素是最大的,最小堆就是堆顶的元素是最小的。原理都差不多,我们只分析一个就行了,我们就以数组【10,4,8,3,5,1】为例来画个图分析一下最小堆是怎么创建的。
这就是堆的创建,把元素加入到堆中的时候,都要和父节点进行比对,在最小堆中,如果比父节点小,就要和父节点交换,交换之后还要继续和再和新的父节点对比……。同理在最大堆中,如果比父节点大,就要和父节点交换。
我们看到上面堆创建之后数组的元素顺序变为【1,4,3,10,5,8】
堆的删除堆的添加会往上调整,堆的删除不仅会往下调整而且还有可能往上调整。堆中元素的删除我们可以从堆顶删除,也可以从中间某个位置删除,如果从堆顶删除的话我们只需要往下调整即可,因为堆顶没有父节点,不需要往上调整。如果从中间删除的话,我们先要往下调整,如果往下调整没有成功(比如在最小堆中,他比两个子节点都小),我们还要进行往上的调整。调整的原理就是把数组最后一个元素放到要删除的元素位置上,然后在删除元素的位置上进行上下调整,原理其实都差不多,我们来看一下最小堆顶部元素删除之后的调整。
上面是我们把堆顶元素1删除之后堆的调整,如果我们再把堆顶元素3删除之后,只需要用数组的最后一个元素5替换3,然后再往下调整即可……
代码堆的添加和删除我们都分析过了,如果把前面的分析都搞懂的话,那么堆的代码就很容易写了,我们来看下
1public class MyHeap<E> { 2 private Object[] data;//数据存放区 3 private int size;//堆的大小 4 private Comparator<? super E> comparator;//比较器 5 6 public MyHeap(int initialCapacity) { 7 this(initialCapacity, null); 8 } 9 10 public MyHeap(int initialCapacity, Comparator<? super E> comparator) { 11 if (initialCapacity < 1) 12 throw new IllegalArgumentException("堆的大小必须大于0"); 13 this.data = new Object[initialCapacity]; 14 this.comparator = comparator; 15 } 16 17 /** 18 * @param e 向堆中添加元素 19 * @return 20 */ 21 public boolean add(E e) { 22 if (e == null)//不能为空 23 throw new NullPointerException(); 24 if (size >= data.length)//如果堆的空间不够了就扩容,这里是扩大2倍 25 data = Arrays.copyOf(data, data.length << 1); 26 if (size == 0)//如果堆是空的,直接添加就可以了,不需要调整,因为就一个没发调整 27 data[0] = e; 28 else//如果堆不是空的,就要往上调整。 29 siftUp(e); 30 size++;//添加完之后size要加1 31 return true; 32 } 33 34 public int getSize() { 35 return size; 36 } 37 38 //删除堆顶元素 39 public E remove() { 40 if (size == 0) 41 return null; 42 size--; 43 E result = (E) data[0];//获取堆顶的元素 44 E x = (E) data[size];//取出数组的最后一个元素 45 data[size] = null;//然后把最后一个元素的位置置空 46 if (size != 0) 47 siftDown(x);//这里实际上是把数组的最后一个元素取出放到栈顶,然后再往下调整。 48 return result; 49 } 50 51 //访问堆顶元素,不删除 52 public E peek() { 53 return (size == 0) ? null : (E) data[0]; 54 } 55 56 /** 57 * 返回数组的值 58 * 59 * @param a 60 * @param <T> 61 * @return 62 */ 63 public <T> T[] toArray(T[] a) { 64 if (a.length < size) 65 return (T[]) Arrays.copyOf(data, size, a.getClass()); 66 System.arraycopy(data, 0, a, 0, size); 67 if (a.length > size) 68 a[size] = null; 69 return a; 70 } 71 72 /** 73 * 往上调整,往上调整只需要和父节点比较即可,如果比父节点大就不需要在调整 74 * 75 * @param e 76 */ 77 private void siftUp(E e) { 78 int s = size; 79 while (s > 0) { 80 int parent = (s - 1) >>> 1;//根据子节点的位置可以找到父节点的位置 81 Object pData = data[parent]; 82 //和父节点比较,如果比父节点大就退出循环不再调整 83 if (comparator != null) { 84 if (comparator.compare(e, (E) pData) >= 0) 85 break; 86 } else { 87 if (((Comparable<? super E>) e).compareTo((E) pData) >= 0) 88 break; 89 } 90 //如果比父节点小,就和父节点交换,然后再继续往上调整 91 data[s] = pData; 92 s = parent; 93 } 94 //通过上面的往上调整,找到合适的位置,再把e放进去 95 data[s] = e; 96 } 97 98 /** 99 * 往下调整,往下调整需要和他的两个子节点(如果有两个子节点)都要比较,哪个最小就和哪 100 * 个交换,如果比两个子节点都小就不用再交换 101 * 102 * @param e 103 */ 104 private void siftDown(E e) { 105 int half = size >>> 1; 106 int index = 0; 107 while (index < half) { 108 int min = (index << 1) + 1;//根据父节点的位置可以找到左子节点的位置 109 Object minChild = data[min]; 110 int right = min + 1;//根据左子节点找到右子节点的位置 111 if (right < size) {//如果有右子节点就执行这里的代码 112 //如果有右子节点,肯定会有左子节点。那么就需要左右两个子节点比较,把小的赋值给minChild 113 if (comparator != null) { 114 if (comparator.compare((E) minChild, (E) data[right]) > 0) 115 minChild = data[min = right]; 116 } else { 117 if (((Comparable<? super E>) minChild).compareTo((E) data[right]) > 0) 118 minChild = data[min = right]; 119 } 120 } 121 //用节点e和他的最小的子节点比较,如果小于他最小的子节点就退出循环,不再往下调整了, 122 if (comparator != null) { 123 if (comparator.compare(e, (E) minChild) <= 0) 124 break; 125 } else { 126 if (((Comparable<? super E>) e).compareTo((E) minChild) <= 0) 127 break; 128 } 129 //如果e比它的最小的子节点小,就用最小的子节点和e交换位置,然后再继续往下调整。 130 data[index] = minChild; 131 index = min; 132 } 133 data[index] = e; 134 } 135}
这里的删除和添加操作的都是堆顶的元素,所以添加的时候会调用siftUp进行往上调整,删除的时候会调用siftDown进行往下调整。我把注释都写在代码中了,这里就不再详细介绍。
堆排序通过上面的分析,我们知道最大堆就是堆顶元素始终保持的是最大值,最小堆就是堆顶元素始终保持的是最小值,假如在最小堆中我们把堆顶元素一个个给移除不就相当于排序了吗。我们来测试一下
1 int[] array = {10, 4, 8, 3, 5, 1}; 2 System.out.print("数组原始的值:"); 3 Util.printIntArrays(array); 4 MyHeap myHeap = new MyHeap(10, new Comparator<Integer>() { 5 @Override 6 public int compare(Integer o, Integer t1) { 7 return (o - t1 > 0) ? 1 : -1; 8 } 9 }); 10 11 for (int i = 0; i < array.length; i++) { 12 myHeap.add(array[i]); 13 } 14 System.out.println(); 15 System.out.print("堆中元素的值:"); 16 Util.printObjectArrays(myHeap.toArray(new Object[myHeap.getSize()])); 17 System.out.println(); 18 System.out.print("排序之后的值:"); 19 for (int i = 0, length = myHeap.getSize(); i < length; i++) { 20 System.out.print(myHeap.remove() + "\t"); 21 }
我们来看一下打印结果 1数组原始的值:10 4 8 3 5 1 2堆中元素的值:1 4 3 10 5 8 3排序之后的值:1 3 4 5 8 10
我们看到堆中元素的值是【1,4,3,10,5,8】和我们最开始分析创建堆的结果完全一致。并且最后一行完成了从小到大的顺序输出
总结:上面我们主要分析是最小堆,如果是最大堆代码该怎么写呢,其实有两种方式,一种是直接在上面代码MyHeap类中修改,还一种是在创建构造函数的时候重写比较器Comparator,我们这里推荐使用第二种,比如我们想按照从大到小的顺序输出,我们来看下该怎么写
1 int[] array = {10, 4, 8, 3, 5, 1}; 2 System.out.print("数组原始的值:"); 3 Util.printIntArrays(array); 4 MyHeap myHeap = new MyHeap(10, new Comparator<Integer>() { 5 @Override 6 public int compare(Integer o, Integer t1) { 7 return (o - t1 < 0) ? 1 : -1; 8 } 9 }); 10 11 for (int i = 0; i < array.length; i++) { 12 myHeap.add(array[i]); 13 } 14 System.out.println(); 15 System.out.print("堆中元素的值:"); 16 Util.printObjectArrays(myHeap.toArray(new Object[myHeap.getSize()])); 17 System.out.println(); 18 System.out.print("排序之后的值:"); 19 for (int i = 0, length = myHeap.getSize(); i < length; i++) { 20 System.out.print(myHeap.remove() + "\t"); 21 }
我们只需修改一个字符即可,就是在上面第7行把之前的大于号改为小于号,我们来看下运行结果
1数组原始的值:10 4 8 3 5 1 2堆中元素的值:10 5 8 3 4 1 3排序之后的值:10 8 5 4 3 1
|