Skip to content

replacement for binheap code #941

Description

@wrigjl

The binary heap code looks like it was written by someone learning C++ coming from Python. The proposed code below is more idiomatic C++. I also demonstrated functionality hiding (percUp, percDown, etc. shouldn't be callable outside the heap implementation).

#include <iostream>
#include <vector>
#include <stdexcept>

class BinHeap {
public:
    BinHeap() {
        // make sure the 0th element is present
        heapvector.push_back(0);
        currentSize = 0;
    }

    // insert key "k" into the tree. It may need to percolate up.
    void insert(int k) {
        heapvector.push_back(k);
        currentSize++;
        percUp(currentSize);
    }

    // remove the minimum from the heap
    int delMin() {
        if (currentSize <= 0)
            throw std::runtime_error("Heap is empty");

        const int retval = heapvector[1];
        heapvector[1] = heapvector[currentSize];
        currentSize--;
        heapvector.pop_back();
        percDown(1);
        return retval;
    }

    void buildHeap(const std::vector<int>& avector) {
        currentSize = avector.size();
        heapvector = avector;
        for (size_t i = avector.size() / 2; i > 0; i--)
            percDown(i);
    }

    bool isEmpty() const {
        return currentSize > 0;
    }

    int findMin() const {
        return heapvector[1];
    }

private:
    std::vector<int> heapvector;
    size_t currentSize;

    // return the minimum child of child "i"
    // assumes i has at least one child (left)
    size_t minChild(size_t i) const {
        size_t leftIndex = i * 2;
        size_t rightIndex = i * 2 + 1;

        if (rightIndex > currentSize)
            return leftIndex;
        if (heapvector[leftIndex] < heapvector[rightIndex])
            return leftIndex;
        return rightIndex;
    }

    // percolate the item at position "i" down the tree
    void percDown(size_t i) {
        while ((i * 2) <= currentSize) {
            size_t mc = minChild(i);

            if (heapvector[i] <= heapvector[mc]) {
                // heap property is not violated, we're done
                return;
            }

            // otherwise, swap and continue percolating
            std::swap(heapvector[i], heapvector[mc]);
            i = mc;
        }
    }

    // percolate the item at position "i" up the tree
    void percUp(size_t i) {
        for (; i / 2 > 0; i /= 2) {
            if (heapvector[i] >= heapvector[i/2]) {
                // heap property not violated, we're done
                return;
            }

            // otherwise, swap and continue percolating
            std::swap(heapvector[i], heapvector[i/2]);
        }
    }
};

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions