PriorityQueue< T, Compare > Class Template Reference

#include <data_structures.hpp>

Public Member Functions
bool	empty () const
T	pop ()
void	push (const T &item)
size_t	size () const

Private Member Functions
void	heapify_down (size_t index)
void	heapify_up (size_t index)

Private Attributes
Compare	comp_
std::vector< T >	heap_

Detailed Description

template<typename T, typename Compare = std::less<T>>
class PriorityQueue< T, Compare >

Definition at line 71 of file data_structures.hpp.

Member Function Documentation

empty()

template<typename T , typename Compare = std::less<T>>

bool PriorityQueue< T, Compare >::empty ( ) const

inline

Definition at line 128 of file data_structures.hpp.

                       {
        return heap_.empty();
    }

References PriorityQueue< T, Compare >::heap_.

Referenced by PriorityQueue< T, Compare >::pop(), and TEST().

heapify_down()

template<typename T , typename Compare = std::less<T>>

void PriorityQueue< T, Compare >::heapify_down ( size_t  index )

inlineprivate

Definition at line 88 of file data_structures.hpp.

                                    {
        while (true) {
            size_t largest = index;
            size_t left = 2 * index + 1;
            size_t right = 2 * index + 2;
 
            if (left < heap_.size() && comp_(heap_[largest], heap_[left])) {
                largest = left;
            }
            if (right < heap_.size() && comp_(heap_[largest], heap_[right])) {
                largest = right;
            }
 
            if (largest == index) {
                break;
            }
 
            std::swap(heap_[index], heap_[largest]);
            index = largest;
        }
    }

References PriorityQueue< T, Compare >::comp_, and PriorityQueue< T, Compare >::heap_.

Referenced by PriorityQueue< T, Compare >::pop().

heapify_up()

template<typename T , typename Compare = std::less<T>>

void PriorityQueue< T, Compare >::heapify_up ( size_t  index )

inlineprivate

Definition at line 76 of file data_structures.hpp.

                                  {
        while (index > 0) {
            size_t parent = (index - 1) / 2;
            if (comp_(heap_[parent], heap_[index])) {
                std::swap(heap_[parent], heap_[index]);
                index = parent;
            } else {
                break;
            }
        }
    }

References PriorityQueue< T, Compare >::comp_, and PriorityQueue< T, Compare >::heap_.

Referenced by PriorityQueue< T, Compare >::push().

pop()

template<typename T , typename Compare = std::less<T>>

T PriorityQueue< T, Compare >::pop ( )

inline

Definition at line 116 of file data_structures.hpp.

            {
        if (empty())
            throw std::runtime_error("Queue is empty");
        T result = heap_[0];
        heap_[0] = heap_.back();
        heap_.pop_back();
        if (!empty()) {
            heapify_down(0);
        }
        return result;
    }

References PriorityQueue< T, Compare >::empty(), PriorityQueue< T, Compare >::heap_, and PriorityQueue< T, Compare >::heapify_down().

Referenced by TEST().

push()

template<typename T , typename Compare = std::less<T>>

void PriorityQueue< T, Compare >::push ( const T &  item )

inline

Definition at line 111 of file data_structures.hpp.

                             {
        heap_.push_back(item);
        heapify_up(heap_.size() - 1);
    }

References PriorityQueue< T, Compare >::heap_, and PriorityQueue< T, Compare >::heapify_up().

Referenced by TEST().

size()

template<typename T , typename Compare = std::less<T>>

size_t PriorityQueue< T, Compare >::size ( ) const

inline

Definition at line 131 of file data_structures.hpp.

                        {
        return heap_.size();
    }

References PriorityQueue< T, Compare >::heap_.

Member Data Documentation

comp_

template<typename T , typename Compare = std::less<T>>

Compare PriorityQueue< T, Compare >::comp_

private

Definition at line 74 of file data_structures.hpp.

Referenced by PriorityQueue< T, Compare >::heapify_down(), and PriorityQueue< T, Compare >::heapify_up().

heap_

template<typename T , typename Compare = std::less<T>>

std::vector<T> PriorityQueue< T, Compare >::heap_

private

Definition at line 73 of file data_structures.hpp.

Referenced by PriorityQueue< T, Compare >::empty(), PriorityQueue< T, Compare >::heapify_down(), PriorityQueue< T, Compare >::heapify_up(), PriorityQueue< T, Compare >::pop(), PriorityQueue< T, Compare >::push(), and PriorityQueue< T, Compare >::size().

---

The documentation for this class was generated from the following file:

• data_structures.hpp