BinaryHeap.h

Go to the documentation of this file.

// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
// SPDX-FileCopyrightText: 2024 Jorrit Rouwe
// SPDX-License-Identifier: MIT
 
#pragma once
 
JPH_NAMESPACE_BEGIN
 
template <typename Iterator, typename Pred>
void BinaryHeapPush(Iterator inBegin, Iterator inEnd, Pred inPred)
{
    using diff_t = typename std::iterator_traits<Iterator>::difference_type;
    using elem_t = typename std::iterator_traits<Iterator>::value_type;
 
    // New heap size
    diff_t count = std::distance(inBegin, inEnd);
 
    // Start from the last element
    diff_t current = count - 1;
    while (current > 0)
    {
        // Get current element
        elem_t &current_elem = *(inBegin + current);
 
        // Get parent element
        diff_t parent = (current - 1) >> 1;
        elem_t &parent_elem = *(inBegin + parent);
 
        // Sort them so that the parent is larger than the child
        if (inPred(parent_elem, current_elem))
        {
            std::swap(parent_elem, current_elem);
            current = parent;
        }
        else
        {
            // When there's no change, we're done
            break;
        }
    }
}
 
template <typename Iterator, typename Pred>
void BinaryHeapPop(Iterator inBegin, Iterator inEnd, Pred inPred)
{
    using diff_t = typename std::iterator_traits<Iterator>::difference_type;
 
    // Begin by moving the highest element to the end, this is the popped element
    std::swap(*(inEnd - 1), *inBegin);
 
    // New heap size
    diff_t count = std::distance(inBegin, inEnd) - 1;
 
    // Start from the root
    diff_t largest = 0;
    for (;;)
    {
        // Get first child
        diff_t child = (largest << 1) + 1;
 
        // Check if we're beyond the end of the heap, if so the 2nd child is also beyond the end
        if (child >= count)
            break;
 
        // Remember the largest element from the previous iteration
        diff_t prev_largest = largest;
 
        // Check if first child is bigger, if so select it
        if (inPred(*(inBegin + largest), *(inBegin + child)))
            largest = child;
 
        // Switch to the second child
        ++child;
 
        // Check if second child is bigger, if so select it
        if (child < count && inPred(*(inBegin + largest), *(inBegin + child)))
            largest = child;
 
        // If there was no change, we're done
        if (prev_largest == largest)
            break;
 
        // Swap element
        std::swap(*(inBegin + prev_largest), *(inBegin + largest));
    }
}
 
JPH_NAMESPACE_END