Java代码为例讲解堆的性质和基本操作以及排序方法
堆的性质
堆是一棵完全二叉树,实际中可以通过一个数组来实现,它最重要的一个性质是:任意节点都小于(大于)等于其子节点。将根节点最小的堆称为最小堆,根节点最大的堆称为最大堆。下图给出了一个最大堆的示例及其数组表示,可以直观地看出每个节点都比它的孩子们都要大。
在上图中可以看到,完全二叉树的节点可以从根节点编号为1开始按顺序排列,对应数组A中的索引(注意此处下标是从1开始的)。给定一个节点i,我们很容易可以得到它的左孩子是2i,右孩子是2i+1,父节点是i/2
堆的基本操作
堆有两种基本操作(下面以最小堆为例):
插入元素k:直接将k添加到数组最后,然后向上冒泡(bubble-up)调整堆。向上冒泡操作:将要调整的元素与其父节点比较,如果大于其父节点则交换,直到恢复堆的性质。
提取最值:最值即根元素。然后将其删除,令根元素=最后的叶子结点元素,然后从根元素开始向下冒泡(bubble-down)调整堆。向下冒泡操作:每次应该从要调整节点,其左右孩子一共三个节点中选择最小的子节点来交换(如果最小就是其本身就不用交换),直到恢复堆的性质。
实际中经常需要将一个包含n个元素无序数组建立成堆,下面的Heap类中的构造方法将展示如何通过_bubbleDown向下冒泡调整来建堆。堆实质上是一棵完全二叉树,树高总为lognlogn,每种基本操作的耗时操作都在于冒泡调整以满足堆的性质,因此它们的时间复杂度都是O(nlogn)O(nlogn)。
Java示例:
//上浮 public void swim(int k){ while(k/2>=1 && less(pq[k/2],pq[k])){ exch(pq,k/2,k); k=k/2; } } //下沉 private void sink() { int k=1; while(2*k<N){ int j=2*k; if(less(pq[j],pq[j+1])) j++; if(less(pq[k],pq[j])) exch(pq,k,j); else break; k = j; } }
堆排序实现原理
分为两步:
1.把数组排成二叉堆的顺序
2.调换根节点和最后一个节点的位置,然后对根节点进行下沉操作。
实现:
可能我的代码和上面的动画略有出入,不过基本原理差不多。
public class HeapSort extends BaseSort { private int N; @Override public void sort(Comparable[] a) { N =a.length-1; int k = N/2; while(k>=1){ sink(a,k); k--; } k = 1; while(k<=N){ exch(a,k,N--); sink(a,k); } } }
赞 (0)