堆排序及top k 问题

一：堆排序

1.向上调整建堆

2.向下调整建堆

3.向上调整建堆时间复杂度

4.向下调整建堆时间复杂度

二：找 top k 问题

1.造数据

2.进行建堆，查找最大的K个数据

一：堆排序

升序 --- 建大堆 --- 每个父亲节点 >= 孩子节点

降序 --- 建小堆 --- 每个父亲节点 <= 孩子节点

在此处我们需要一个堆，参考http://t.csdn.cn/GDbI9

在上述链接中建立的为小堆。

小堆 --- 选出最小的，然后进行首尾交换，将最小的一个放在最后一个位置。

然后，把最后一个不看作堆里面的。向下调整，选出次小的数据，循环往反上述过程。

1.向上调整建堆

//建堆
int i = 0;
//向上调整建堆
for (i = 0; i < n; i++)
{

//传入数组孩子的下标
AdjustUp(a, i);
}

//在下一个数据插入时，已经为堆（前面的值可以构成堆）

代码为：

//堆排序
void HeapSort(int* a, int n)
{//升序 --- 建大堆//降序 --- 建小堆//建堆int i = 0;//向上调整建堆for (i = 0; i < n; i++){AdjustUp(a, i);}//向下调整建堆//for (i = (n - 1 - 1) / 2; i >= 0; i--)//{//	AdjustDown(a, n, i);//}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);//在调整 --- 选出次小的数AdjustDown(a, end, 0);--end;}
}
int main()
{int a[10] = { 1,2,3,4,5,6,8,7,9,0};int n = sizeof(a) / sizeof(a[0]);HeapSort(a, n);
}

运行效果为：

2.向下调整建堆

//向下调整建堆
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{

//传入数组数组的大小数组下标
AdjustDown(a, n, i);
}

//父亲节点 = （孩子节点 - 1 ） / 2

//从倒数第一个非叶节点开始调

代码为：

//堆排序
void HeapSort(int* a, int n)
{//升序 --- 建大堆//降序 --- 建小堆//建堆int i = 0;向上调整建堆//for (i = 0; i < n; i++)//{//	AdjustUp(a, i);//}//向下调整建堆for (i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);//在调整 --- 选出次小的数AdjustDown(a, end, 0);--end;}
}
int main()
{int a[10] = { 1,2,3,4,5,6,8,7,9,0};int n = sizeof(a) / sizeof(a[0]);HeapSort(a, n);
}

运行效果为：

3.向上调整建堆时间复杂度

4.向下调整建堆时间复杂度

二：找 top k 问题

即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

假设：有N个数，找其中得最大/最小的 K 个数

方案一：

将N个数建成一个大堆，Pop K次，即可以求出最大的前K个，该方法在N特别大的时候，解决不了问题。

方案二：

将前K个数建立一个小堆

后面的N-K个数，依次比较，如果比堆顶数据大，就替换堆顶数据进堆（覆盖堆顶数据，向下调整）

最后这个小堆的值，就是前K个

1.造数据

需要先造出N个数据

CreateNDate();

产生随机数的函数：srand

获取系统时间：time

在造数据的时候，我们可以将所造的数据存储在一个文件中 --- data.txt

关于文件操作，可以参考：http://t.csdn.cn/qejfU

代码为：

//找 topK 问题
void CreateNDate()
{// 造数据int n = 10000;srand(time(0));const char* file = "data.txt";//fopen --- 打开文件//FILE *fopen( const char *filename, const char *mode );//              文件名                  打开方式FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){//rand --- 获取随机数//int rand( void );int x = rand() % 1000000;//fprintf --- 向文件写入格式化的内容//int fprintf( FILE *stream, const char *format [, argument ]...);//对比 printf 函数 //int printf( const char *format [, argument]... );fprintf(fin, "%d\n", x);}//fclose --- 关闭文件//int fclose( FILE *stream );//             目标文件fclose(fin);
}int main()
{CreateNDate();//PrintTopK(8);return 0;
}

结果为：

生成的数据

2.进行建堆，查找最大的K个数据

需要先以只读的方式，打开数据所在的 --- data.txt ，然后读取（fscanf)前K个数据将其采用向下调整建堆的方式放在一个数组中（在此处，需要先开辟好一个数组用于存放数据），然后依次去读取剩下的N-K个数据，让其分别于堆顶数据(堆顶数据为堆内最小的数据 --- 小堆）进行比较，如果比堆顶数据大，则覆盖堆顶数据，然后进行向下调整算法，然后打印出数组中的内容，以上操作进行完毕后，关闭文件。

代码为：

//向下调整算法
//在此处先设计改为小根堆 --- 每个父亲都 <= 孩子 
void AdjustDown(int* a, int* n, int parent)
{//对其逻辑结构进行分析，如果没有左孩子，则一定没有右孩子int child = parent * 2 + 1;//左孩子while (child < n){//找到左右孩子中的较小孩子 --- 判断右孩子存在//                             有左孩子不一定有右孩子 --- 右孩子要先存在，才能与左孩子进行比较，注意写代码时的顺序if ( child + 1 < n && a[child] > a[child + 1])//左孩子大于右孩子，则 child 为右孩子，上述假设时，假设的为左孩子小{++child;}//找到较小的孩子，与父亲节点进行比较，若比其小，让其与其父亲节点进行交换if (a[parent] > a[child]){Swap(&a[parent], &a[child]);//让小的节点向上走，大节点向下走parent = child;child = parent * 2 + 1;//循环更替条件}else{break;}}
}

void PrintTopK(int k)
{//先建立一个小堆，存放 k 个数据，然后用其他数据与堆顶数据做对比，如果比堆顶数据大，将堆顶覆盖//小根堆：每个父亲结点 <= 孩子结点//以读的方式打开const char* file = "data.txt";FILE* fout = fopen(file,"r");if (fout == NULL){perror("fopen error");return;}//读取k个数据放到数组里面 --- 开辟数组用于存放int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail\n");return;}int i = 0;for (i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}//建小堆for (i = (k - 1 - 1); i >= 0; i--){//进行调整AdjustDown(kminheap,k,i);}int val = 0;while (!feof(fout)){fscanf(fout, "%d", &val);if (val > kminheap[0]){kminheap[0] = val;AdjustDown(kminheap, k, 0);}}for (i = 0; i < k; i++){printf("%d\n", kminheap[i]);}printf("\n");fclose(fout);
}

效果为：