参考答案

参考回答:

#include <iostream>
using namespace std;

//将有二个有序数列a[first...mid]和a[mid...last]合并。

void __merge(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void __merge_sort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
__merge_sort(a, first, mid, temp);
__merge_sort(a, mid + 1, last, temp);
__merge(a, first, mid, last, temp);
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
{
return false;
}
else
{
__merge_sort(a, 0, n - 1, p);
delete[] p;
return true;
}
}
int main()
{
const int LEN = 10;
int a[LEN] = { 23, 40, 45, 19, 12, 16, 90, 39, 87, 71 };
cout<<"Before the merge sort, the Array is:"<<endl;
for(int i = 0; i < LEN; ++i)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<endl;
MergeSort(a, LEN);
cout<<"After the merge sort, the Array is:"<<endl;
for(int i = 0; i < LEN; ++i)
{
cout<<a[i]<<" ";
}
cout<<endl;
system("pause");
return 0;
}

小顶堆：

import java.util.Arrays;
public class SmallHeap {
public static int[] topN(int[] arr, int n) {
int[] list = new int[n];
System.arraycopy(arr, 0, list, 0, n);
for (int i = 0; i < n; i++) {
int t = i;
while (t != 0 && list[parent(t)] > list[t]) {
swap(list, t, t = parent(t));
}
}
for (int i = n, len = arr.length; i < len; i++) {
if (arr[i] >= list[0]) {

// 置换栈顶

list[0] = arr[i];

// 调整栈顶

int t = 0;
while((left(t)<n&&list[t]>list[left(t)])||(right(t)<n&& list[t]>list[right(t)])) {
if (right(t) < n && list[right(t)] < list[left(t)]) {
swap(list, t, t = right(t));
} else {
swap(list, t, t = left(t));
}
}
}
}
return list;
}
private static void swap(int[] list, int i, int j) {
int tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
private static int parent(int i) {
return (i - 1) / 2;
}
private static int left(int i) {
return 2 * i + 1;
}
private static int right(int i) {
return 2 * i + 2;
}
public static void main(String[] args) {
int[] arr = new int[]{56, 30, 71, 18, 29, 93, 44, 75, 20, 65, 68, 34};

System.out.println("原始数组: ");

System.out.println(Arrays.toString(arr));

System.out.println("调整后数组: ");

System.out.println(Arrays.toString(SmallHeap.topN(arr, 5)));

}

}