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 OS_PTHREADS_MAX_HEAP_HPP
#define OS_PTHREADS_MAX_HEAP_HPP
 
#include <FpConfig.hpp>
 
namespace Os {
 
  class MaxHeap {
 
    public:
    MaxHeap();
    ~MaxHeap();
    bool create(NATIVE_UINT_TYPE capacity);
    bool push(NATIVE_INT_TYPE value, NATIVE_UINT_TYPE id);
    bool pop(NATIVE_INT_TYPE& value, NATIVE_UINT_TYPE& id);
    bool isFull();
    bool isEmpty();
    NATIVE_UINT_TYPE getSize();
    void print();
 
    private:
    // Private functions:
    // Ensure the heap meets the heap property:
    void heapify();
    // Swap two elements on the heap:
    void swap(NATIVE_UINT_TYPE a, NATIVE_UINT_TYPE b);
    // Return the max between two elements on the heap:
    NATIVE_UINT_TYPE max(NATIVE_UINT_TYPE a, NATIVE_UINT_TYPE b);
 
    // The data structure for a node on the heap:
    struct Node {
      NATIVE_INT_TYPE value; // the priority of the node
      NATIVE_UINT_TYPE order; // order in which node was pushed
      NATIVE_UINT_TYPE id; // unique id for this node
    };
 
    // Private members:
    Node* m_heap; // the heap itself
    NATIVE_UINT_TYPE m_size; // the current size of the heap
    NATIVE_UINT_TYPE m_order; // the current count of heap pushes
    NATIVE_UINT_TYPE m_capacity; // the maximum capacity of the heap
  };
 
}
 
#endif // OS_PTHREADS_MAX_HEAP_HPP