0.前置知识
向上调整:
向下调整:
1.对一个无序的数组排升序和降序
排升序问题
错误想法
由小根堆的定义:树中所有的父节点的值都小于或等于孩子节点的值,这样排出来的数组时升序的,建小根堆调用向上调整函数即可(把画圈的地方改成<即可)
arr未排序时,为{2,1,5,7,6,8,0,9,4,3}
执行结果
显然不是升序
错误原因:忽略了一个严重的前提: 向上调整的前提:除了child位置,前面的数据结构构成堆
AdjustUp虽然找到了数组中最小的数,将其放到堆顶,但是堆顶的左右子树是无序的,必须将堆顶元素pop后才能选出剩余元素中最小的
解决方法
1.重新建堆:时间复杂度过高,不建议使用
2.建大根堆
代码
typedef int HPDataType;void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (parent>=0){if (a[child] > a[parent]){Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child+1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}
}void HeapSort(int* arr, int n)
{for (int i = 1; i < n; i++){AdjustUp(arr, i);}int end = n - 1;while (end > 0){Swap(&arr[end], &arr[0]);AdjustDown(arr, end, 0);end--;}
}int main()
{int arr[] = {2,1,5,7,6,8,0,9,4,3};int size = sizeof(arr)/sizeof(arr[0]);HeapSort(arr,size);return 0;
}运行结果
细节分析
将HeapSort的while循环删掉,在return 0;处下断点,监视窗口查看arr
建大堆后
要好好利用大堆的这一个性质:堆顶元素的值永远是堆中元素的最大值
用while反复调整的过程可以描述为:
大堆2=={大堆3,大堆2中最大的元素} -->大堆1=={大堆3,大堆2中最大的元素,大堆1中最大的元素}
...
将上方的式子合并起来,有
大堆1={大堆n,大堆(n-1)中最大的元素,大堆(n-2)中最大的元素,...,大堆2中最大的元素,大堆1中最大的元素}
满足升序的要求
思考题
改动以上代码，使其对数组排降序
答案:理解上述分析的核心要点后,只需要改动几个不等号就可以了
typedef int HPDataType;void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (parent >= 0){if (a[child] < a[parent]){Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}
}void HeapSort(int* arr, int n)
{for (int i = 1; i < n; i++){AdjustUp(arr, i);}int end = n - 1;while (end > 0){Swap(&arr[end], &arr[0]);AdjustDown(arr, end, 0);end--;}
}int main()
{int arr[] = { 2,1,5,7,6,8,0,9,4,3 };int size = sizeof(arr) / sizeof(arr[0]);HeapSort(arr, size);return 0;
}运行结果
