//调整堆（小顶堆）
void HeapAdjust(int A[],int parent,int length)
{
//temp保存当前父节点parent
int temp=A[parent];
//左子结点开始，i节点的左孩子为2i+1，右孩子为2i+2
for(int child=2*parent+1;child<length;child=2*child+1)
{
//如果右子节点存在，且右子结点小于左子结点，则指向右子结点
if(child+1<length && A[child]>A[child+1])
child++;
//如果（左或右）子节点小于父节点，将子节点值赋给父节点（不用进行交换）
if(A[child]<temp)
{
A[parent]=A[child];
parent=child;//选取孩子结点的左孩子结点,child=2*child+1，继续向下筛选
}
else //若父节点小于（左和右）孩子节点 ，则直接结束
break;
}
A[child]=temp;//将temp的值放到最终的位置
}
//建立堆
void HeapBuild(int A[],int length)
{
for(int i=length/2-1;i>=0;i--)
HeapAdjust(A,i,length)
}
//利用堆找出最小的k个数（小顶堆）
int getKMinusByHeap(int read[],int k)
{
if(k<1 || k>read.length())
return -1;
int kHeap = new int[k]; //存储k个堆元素
//初始时一次性从文件中读取k个数据到堆中
for(int i=0;i<k;i++)
kHeap[i]=read[i];
HeapBuild(kHeap,k); //建小顶堆堆，时间复杂度O(k)
// 从文件中一个一个的读取剩余数据
for(int i=k;i<read.length();i++)
{
if(read[i]<kHeap[0]) //读入的元素小于堆顶元素
{
kHeap[0]=read[i];
HeapAdjust(kHeap,0,k);// 从堆顶开始向下进行调整，时间复杂度O(logk)
}
}
return kHeap;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/162909.html
![[译]BNF 表示法：深入了解 Python 的语法](https://www.bmabk.com/wp-content/uploads/2022/05/post-loading-480x300.gif)
