MaxHeap.hpp

Go to the documentation of this file.

// ======================================================================
// \title  MaxHeap.hpp
// \author dinkel
// \brief  An implementation of a stable max heap data structure
//
// \copyright
// Copyright 2009-2015, by the California Institute of Technology.
// ALL RIGHTS RESERVED.  United States Government Sponsorship
// acknowledged.
//
// ======================================================================

#ifndef UTILS_TYPES_MAX_HEAP_HPP
#define UTILS_TYPES_MAX_HEAP_HPP

#include <FpConfig.hpp>

namespace Types {

class MaxHeap {
  public:
    MaxHeap();
    ~MaxHeap();
    bool create(FwSizeType capacity);
    bool push(FwQueuePriorityType value, FwSizeType id);
    bool pop(FwQueuePriorityType& value, FwSizeType& id);
    bool isFull();
    bool isEmpty();
    FwSizeType getSize() const;

  private:
    // Private functions:
    // Ensure the heap meets the heap property:
    void heapify();
    // Swap two elements on the heap:
    void swap(FwSizeType a, FwSizeType b);
    // Return the max between two elements on the heap:
    FwSizeType max(FwSizeType a, FwSizeType b);

    // The data structure for a node on the heap:
    struct Node {
        FwQueuePriorityType value;  // the priority of the node
        FwSizeType order;           // order in which node was pushed
        FwSizeType id;              // unique id for this node
    };

    // Private members:
    Node* m_heap;           // the heap itself
    FwSizeType m_size;      // the current size of the heap
    FwSizeType m_order;     // the current count of heap pushes
    FwSizeType m_capacity;  // the maximum capacity of the heap
};

}  // namespace Types

#endif  // UTILS_TYPES_MAX_HEAP_HPP