积分商城

最新搜索： stm32f0 usb源码 随身听 I9300 Authorware 4.0 DfuSe SSD1306
您现在的位置是：首页 > 技术资料 > 堆的高级应用：堆排序 TopK与中位数维护.doc
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

堆的高级应用：堆排序 TopK与中位数维护.doc

更新时间：2026-10-15 20:39:51 大小：38K 上传用户：潇潇江南查看TA发布的资源 标签：堆排序TopK中位数维护最大堆时间复杂度 下载积分：2分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

堆的高级应用：堆排序、TopK与中位数维护

一、堆排序的深入分析

堆排序利用最大堆实现原地排序，时间复杂度O(n log n)，空间O(1)。

void heapSort(int *arr, int n) {
    // 1. 建堆
    for (int i = n/2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 2. 逐个取出堆顶
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);      // 堆顶与末尾交换
        heapify(arr, i, 0);          // 重建堆
    }
}

void heapify(int *arr, int n, int i) {
    int largest = i;
    int left = 2*i + 1, right = 2*i + 2;
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}


部分文件列表

文件名 大小
堆的高级应用：堆排序、TopK与中位数维护.docx 38K

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号