【数据结构】--》堆的应用

上篇博客对堆的一些基本实现，现在来实现堆的两个应用：

 **海量TopK问题（这里仅用一小部分数据进行测试）---》堆排序**

1，堆排序的实现代码：

此处com使用来传一个函数指针，方便指定升序还是降序，本次是按升序来测试;

void HeapSort(Heap* hp, DataType arr[], int size, Compare com)
{
    assert(hp);
    int i = size - 1;
    CreateHeap(hp, arr, size, com);
    while (i>=0)
    {
        swap(&(hp->_array[0]),&( hp->_array[hp->_size - 1]));
        swap(&arr[i--], &(hp->_array[hp->_size - 1]));
        hp->_size--;
        AdjustDown(hp, 0, com);
    }
}

堆排序的测试代码：

void testHeapSort()
{
    Heap hp;
    int i = 0;
    Compare com = Greater;
    InitHeap(&hp, com);
    DataType arr[] = { 10, 50, 32, 5, 76, 9, 40, 88 };
    int size = sizeof(arr) / sizeof(arr[0]);
    for (; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    HeapSort(&hp, arr, size, com);
    for (int i=0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
}

- 2，海量TopK的问题实现代码：
此处com使用来传一个函数指针，方便指定找最大的前K个数还是最小的前K个数

void TopK(Heap *hp,DataType arr[], int K,int size,Compare com)
{
    assert(hp);
    CreateHeap(hp, arr, K, com);
    while (K<=size)
    {
        if (arr[K] > hp->_array[0])
        {
            hp->_array[0] = arr[K];
            AdjustDown(hp, 0, com);
        }
        K++;
    }
    printf("TopK元素分别是： ");
    for (int i = 0; i <hp->_size; i++)
    {
        printf(" %d ", hp->_array[i]);
    }
}

海量TopK的测试代码：

void testTopK()
{
    Heap hp;
    InitHeap(&hp,less);
    int arr[] = { 1, 3, 5, 4, 5, 6, 8, 9, 0, 78, 6, 56, 34, 23, 167, 56, 435326, 23, 546, 769, 87, 90, 8, 6, 756756 };
     TopK(&hp,arr,5,sizeof(arr)/sizeof(arr[0]),less);
}

——————————————————THANKS————————————————————————