java 初始化堆数据结构

发布于 2024-12-23 17:16:58 字数 41 浏览 1 评论 0原文

如何用简单、基本的 Java 伪代码用 7 个数字初始化堆数据结构？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

十六岁半 2024-12-30 17:16:58

如果您想自己做而不是使用 Java 的 PriorityQueue，那么您必须将所有 X 项放在正确的位置，以便它们维护堆属性：

//This will switch the current item with it's greatest child, if this child is
//larger than the current item itself.
private void percolateDown(int i){
    //Get n's greatest child. The two children are at position 2i+1 and 2i+2
    int n = getGreatestChild(i);

    //Don't do anything if the greater child is smaller or equal to the parent
    if( yourNumbersArray[n] <= yourNumbersArray[i] )
        return;

    //Now switch the parent with the greatest child

    //Make sure that the newly placed item is at the right spot by percolating it again.
    percolateDown(n);
}

private void initialize(){
    //Call the percolateDown() function for all items of your array.
    //Due to the heap nature you can leave out the second half, though. 
    int mid = yourNumbersArray.length/2;

//Start in the middle and work your way towards the front.
//This way you'll first sort the lowest level of your heap, then the second lowest, and so on.
    for(; mid>=0; --mid){
        percolateDown(mid);
    }
}

在查找任何项的最大子项时，您必须记住一个或两个子项可能是在你的数组之外。当然，在这种情况下您不必考虑它。

If you want to do it yourself and not use Java's PriorityQueue then you have to put all X items at the right place so they uphold heap properties:

//This will switch the current item with it's greatest child, if this child is
//larger than the current item itself.
private void percolateDown(int i){
    //Get n's greatest child. The two children are at position 2i+1 and 2i+2
    int n = getGreatestChild(i);

    //Don't do anything if the greater child is smaller or equal to the parent
    if( yourNumbersArray[n] <= yourNumbersArray[i] )
        return;

    //Now switch the parent with the greatest child

    //Make sure that the newly placed item is at the right spot by percolating it again.
    percolateDown(n);
}

private void initialize(){
    //Call the percolateDown() function for all items of your array.
    //Due to the heap nature you can leave out the second half, though. 
    int mid = yourNumbersArray.length/2;

//Start in the middle and work your way towards the front.
//This way you'll first sort the lowest level of your heap, then the second lowest, and so on.
    for(; mid>=0; --mid){
        percolateDown(mid);
    }
}

When looking for the greatest child of any item you have to remember that one or both children could be outside of your array. In this case you don't have to take it into account, of course.

回复收藏 0 原文