Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Namespaces | Macros
tpl_binHeap.H File Reference
Trees

Binary heap implementation using tree structure. More...

#include <htlist.H>
#include <tpl_arrayStack.H>
#include <tpl_binNode.H>
#include <tpl_dynListQueue.H>
Include dependency graph for tpl_binHeap.H:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

class  Aleph::BinHeapNode_Data
 
struct  Aleph::BinHeapNode_Data::Control_Fields
 
class  Aleph::BinHeapNode< Key >
 
class  Aleph::BinHeapNodeVtl< Key >
 
class  Aleph::GenBinHeap< NodeType, Key, Compare >
 Heap genérico de nodos. More...
 
class  Aleph::GenBinHeap< NodeType, Key, Compare >::Iterator
 
struct  Aleph::BinHeap< Key, Compare >
 Node heap without virtual destructor. More...
 
struct  Aleph::BinHeapVtl< Key, Compare >
 Heap of nodes with virtual destroyer. More...
 

Namespaces

namespace  Aleph
 Main namespace for Aleph-w library functions.
 

Macros

#define PREV(p)   (p->getL())
 
#define NEXT(p)   (p->getR())
 
#define ULINK(p)   reinterpret_cast<Node*&>((p)->getU())
 
#define IS_LEAF(p)   ((p)->get_control_fields().is_leaf)
 
#define IS_LEFT(p)   ((p)->get_control_fields().is_left)
 
#define CTRL_BITS(p)   ((p)->get_control_fields())
 

Detailed Description

Binary heap implementation using tree structure.

This file provides a binary heap implementation that uses a binary tree structure instead of an array. This allows for dynamic sizing and efficient node-based operations.

Heap Types

  • GenBinHeap: Generic base heap with customizable comparison
  • BinHeap: Min-heap (smallest element at root)
  • BinHeapMax: Max-heap (largest element at root)
  • BinHeapVtl: Min-heap with virtual destructor for polymorphism

Key Features

  • Tree-based structure (not array-based)
  • Parent pointers for efficient operations
  • Supports iteration via Iterator class
  • Move semantics for efficient transfers

Complexity

Operation Time
insert O(log n)
getMin/getMax O(1)
remove O(log n)
update O(log n)
build from n elements O(n)

Usage Example

BinHeap<int> heap;
heap.insert(5);
heap.insert(3);
heap.insert(7);
while (!heap.is_empty()) {
int min = heap.getMin(); // Get minimum
heap.getMin(); // Remove minimum
}
min
__gmp_expr< typename __gmp_resolve_expr< T, V >::value_type, __gmp_binary_expr< __gmp_expr< T, U >, __gmp_expr< V, W >, __gmp_min_function > > min(const __gmp_expr< T, U > &expr1, const __gmp_expr< V, W > &expr2)
Definition gmpfrxx.h:4111

When to Use

Use tree-based heap when:

  • Need dynamic resizing without reallocation
  • Working with node pointers directly
  • Need to update priorities of existing nodes

For array-based heaps (more cache-friendly), see:

See also
tpl_arrayHeap.H Array-based heap implementation
tpl_dynBinHeap.H Dynamic heap with key updates
tpl_fibonacci_heap.H Fibonacci heap for advanced priority queues
Author
Leandro Rabindranath León

Definition in file tpl_binHeap.H.

Macro Definition Documentation

◆ CTRL_BITS

#define CTRL_BITS (   p)    ((p)->get_control_fields())

Definition at line 146 of file tpl_binHeap.H.

◆ IS_LEAF

#define IS_LEAF (   p)    ((p)->get_control_fields().is_leaf)

Definition at line 144 of file tpl_binHeap.H.

◆ IS_LEFT

#define IS_LEFT (   p)    ((p)->get_control_fields().is_left)

Definition at line 145 of file tpl_binHeap.H.

◆ NEXT

#define NEXT (   p)    (p->getR())

Definition at line 142 of file tpl_binHeap.H.

◆ PREV

#define PREV (   p)    (p->getL())

Definition at line 141 of file tpl_binHeap.H.

◆ ULINK

#define ULINK (   p)    reinterpret_cast<Node*&>((p)->getU())

Definition at line 143 of file tpl_binHeap.H.