feisty meow concerns codebase  2.140
Public Member Functions | List of all members
algorithms::heap< type > Class Template Reference

#include <sorts.h>

Public Member Functions

 heap (type to_sort[], int n, bool reverse)
 
void swap_values (int a, int b)
 swaps the values in the heap stored at positions a and b. More...
 
int parent_index (int i)
 get the index of the parent of the node at i. More...
 
int left_child (int i)
 returns the left child of node at position i. More...
 
int right_child (int i)
 returns the right child of node at position i. More...
 
void heapify ()
 re-sorts the heapspace to maintain the heap ordering. More...
 
void sift_down (int start, int end)
 
void alt_heapify ()
 re-sorts the heapspace to maintain the heap ordering. this uses sift_up. More...
 
void sift_up (int start, int end)
 start is how far up in the heap to sort. end is the node to sift. More...
 

Detailed Description

template<class type>
class algorithms::heap< type >

a heap is a structure that can quickly return the highest (or lowest) value, depending on how the priority of the item is defined. a "normal" heap keeps the highest element available first; a reverse sorted heap keeps the lowest element available first. restructuring the heap is fast, and is O(n log(n)). the implicit structure is a binary tree represented in a flat array, where the children of a node at position n are in positions n * 2 + 1 and n * 2 + 2 (zero based).

Definition at line 156 of file sorts.h.

Constructor & Destructor Documentation

◆ heap()

template<class type >
algorithms::heap< type >::heap ( type  to_sort[],
int  n,
bool  reverse 
)
inline

Definition at line 159 of file sorts.h.

References algorithms::heap< type >::heapify().

Member Function Documentation

◆ alt_heapify()

template<class type >
void algorithms::heap< type >::alt_heapify ( )
inline

re-sorts the heapspace to maintain the heap ordering. this uses sift_up.

Definition at line 240 of file sorts.h.

References algorithms::heap< type >::sift_up().

◆ heapify()

template<class type >
void algorithms::heap< type >::heapify ( )
inline

re-sorts the heapspace to maintain the heap ordering.

Definition at line 195 of file sorts.h.

References algorithms::heap< type >::parent_index(), and algorithms::heap< type >::sift_down().

Referenced by algorithms::heap< type >::heap().

◆ left_child()

template<class type >
int algorithms::heap< type >::left_child ( int  i)
inline

returns the left child of node at position i.

Definition at line 183 of file sorts.h.

◆ parent_index()

template<class type >
int algorithms::heap< type >::parent_index ( int  i)
inline

get the index of the parent of the node at i.

this will not return the parent index of the root, since there is no parent.

Definition at line 177 of file sorts.h.

Referenced by algorithms::heap< type >::heapify(), and algorithms::heap< type >::sift_up().

◆ right_child()

template<class type >
int algorithms::heap< type >::right_child ( int  i)
inline

returns the right child of node at position i.

Definition at line 189 of file sorts.h.

◆ sift_down()

template<class type >
void algorithms::heap< type >::sift_down ( int  start,
int  end 
)
inline

Definition at line 206 of file sorts.h.

Referenced by algorithms::heap_sort(), and algorithms::heap< type >::heapify().

◆ sift_up()

template<class type >
void algorithms::heap< type >::sift_up ( int  start,
int  end 
)
inline

start is how far up in the heap to sort. end is the node to sift.

Definition at line 251 of file sorts.h.

References algorithms::heap< type >::parent_index(), and algorithms::heap< type >::swap_values().

Referenced by algorithms::heap< type >::alt_heapify().

◆ swap_values()

template<class type >
void algorithms::heap< type >::swap_values ( int  a,
int  b 
)
inline

swaps the values in the heap stored at positions a and b.

Definition at line 168 of file sorts.h.

Referenced by algorithms::heap_sort(), and algorithms::heap< type >::sift_up().

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