AcWing 838. 堆排序
原题链接
简单
作者:
后来_7
,
2019-08-30 10:17:43
,
所有人可见
,
阅读 1365
java代码
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextInt();
// 对数组的前n个元素建堆
heapify(arr, n);
// 堆排序,保存堆顶元素到数组的末尾
for (int i = n - 1; i > 0; i--) {
int tmp = arr[i];
arr[i] =arr[0];
arr[0] = tmp;
// heapify(arr, i);// 重新调整堆
// 重新调整堆,只需要将堆顶元素下沉,不需要对整个数组在建堆
siftdown(arr, 0, i);
}
for (int i = 0; i < m; i++) {
System.out.print(arr[i] + " ");
}
}
// heapify建堆就是:从最后一个非叶子节点开始下沉,向前遍历;保持的性质是:父节点要大于孩子节点
private static void heapify(int[] arr, int len) {// 对数组的[0,len-1]进行堆化,前len个元素进行堆化;
int idx = (len - 1 - 1) / 2;//最后一个非叶子节点
for (int i = idx; i >= 0; i--) {//向前遍历
siftdown(arr, i, len);
}
}
// 向堆中添加元素是上浮操作
private static void siftdown(int[] arr, int k, int len) {// 当前需要下沉的元素索引k,在数组的[0,len-1]共len个元素中下沉
int leftchild = 2 * k + 1;
int rightchild = leftchild + 1;
while (leftchild < len) {// 循环结束条件是:当前节点没有孩子节点,是叶子节点
int j = leftchild;// 需要交换的索引
if (rightchild < len && arr[rightchild] > arr[leftchild]) {
j = rightchild;
}
if (arr[k] >= arr[j]) {// 大根堆,不需要交换
break;
} else {// 进行交换
int tmp = arr[k];
arr[k] = arr[j];
arr[j] = tmp;
k = j;// 更新当前需要下沉的元素索引
}
leftchild = 2 * k + 1;
rightchild = leftchild + 1;
}
}