堆
堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:
- 堆中某个结点的值总是不大于或不小于其父结点的值;
- 堆总是一棵完全二叉树。
将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。
例如:

构建堆
数组和堆的特点
- 使用一维数组来表示一个堆,下标从0~n,0表示堆顶
- 如果一个节点的下标为x,那么左子节点的下标为 2x+1,右子节点的下标为2x+2
- 如果一个节点的下标为x,那么父节点的下标为(x-1)/2
堆化
在一个已经是最大堆(或者最小堆)的末尾插入一个数据,有可能会打破这个最大堆(或者最小堆)
如下图,在一个最大堆末尾插入一个14的数据,就打破了这个最大堆。这时需要进行堆化处理。

处理方式就是,用这个插入的节点和其父节点对比,如果比父节点大,则互相交换。

交换后再继续和其父节点比较,直至堆顶。

构建堆
由于堆的节点和数组下标有着明显的对应特征,所以构建一个堆只需要固定的几个临时变量,空间复杂度只有O(1)。
构建一个堆也比较简单:
- 首先认为下标0的数据为堆顶
- 接着认为向这个最大堆(或者最小堆)的末尾(首次下标是1)插入数据
- 处理这个新插入的数,使数据堆化
- 重复2~3的步骤,直至数组最后一个元素
需要注意的是:如果要升序排序,则需要构建最大堆,如果要降序排序,则需要构建最小堆
排序
排序步骤也比较简单,就是在执行剔除堆顶的操作
- 交换堆顶(下标为0)的数据和数组最后一个(首次下标为n)的数据,此时最后一个数据是已升序排列完的数据
- 由于步骤1,导致打破了最大堆(或者最小堆),执行堆化操作
- 再重复1~2 直至整个堆只剩下堆顶一个数据为止
示意图

时间复杂度和空间复杂度
堆的构建时间复杂度:O(n2)
排序时间复杂度:O(nlogn)
稳定性
由于对序列跳跃式维护堆的结构性质,相同值顺序无法得到保障,所以堆排序是不稳定的。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| public void sort(int[] nums){ buildHeap(nums); int point = nums.length - 1; while(point > 0){ int temp = nums[0]; nums[0] = nums[point]; nums[point] = temp; heapity(nums,point); point--; } }
private void heapity(int[] nums, int point) { int index = 0; while(index <= point){ int left = 2 * index + 1; int right = left +1; if(left >= point){ return; }else if(right >= point){ if(nums[left] > nums[index]){ int temp = nums[left]; nums[left] = nums[index]; nums[index] = temp; index = left; }else{ return; } }else{ if(nums[left] >= nums[right] && nums[left] > nums[index]){ int temp = nums[left]; nums[left] = nums[index]; nums[index] = temp; index = left; }else if(nums[right] >= nums[left] && nums[right] > nums[index]){ int temp = nums[right]; nums[right] = nums[index]; nums[index] = temp; index = right; }else{ return; } } } }
private void buildHeap(int[] nums) { for (int i = 1; i < nums.length; i++) { buildHeap(nums,i); } }
private void buildHeap(int[] nums,int index) { while(index > 0 ) { int parentIndex = (index-1) / 2; if (nums[parentIndex] < nums[index]) { int temp = nums[parentIndex]; nums[parentIndex] = nums[index]; nums[index] = temp; index = parentIndex; } else { return; } } }
|