CCC_Priority_queue Struct Reference

#include <private_priority_queue.h>

Collaboration diagram for CCC_Priority_queue:

Detailed Description

A priority queue is a variation on a heap ordered tree aimed at simple operations and run times that are very close to optimal. The root of the entire heap never has a next, prev, or parent because only a single heap root is allowed. Nodes can have a left child. The direction of the child does not matter to the implementation because there is only one. Then, any node besides the root of the entire heap can be in a ring of siblings with next and previous pointers. Here is a sample heap.

< = next
> = prev
 
    ┌<0>┐
    └/──┘
  ┌<1>─<7>┐
  └/────/─┘
┌<9>┐┌<8>─<9>┐
└───┘└───────┘

The heap child rings are circular doubly linked lists to support fast update and erase operations. This construction gives the following run times.

┌─────────┬─────────┬─────────┬─────────┐
│min      │delete   │increase │insert   │
│         │min      │decrease │         │
├─────────┼─────────┼─────────┼─────────┤
│O(1)     │O(log(N))│o(log(N))│O(1)     │
│         │amortized│amortized│         │
└─────────┴─────────┴─────────┴─────────┘

The proof for the increase/decrease runtime is complicated. The gist is that updating the key is an O(1) operation. However, it restructures the tree in such a way that the next delete min has more work to do. That is why update and delete min have their amortized run times. In practice, the simplicity of the implementation keeps the pairing heap fast and easy to understand. In fact, if nodes are allocated ahead of time in a buffer, the pairing heap beats the binary flat priority queue in the C Container Collection across many operations with the trade-off being more memory consumed.

Data Fields
struct CCC_Priority_queue_node *	root
size_t	count
size_t	type_intruder_offset
size_t	sizeof_type
CCC_Order	order
CCC_Type_comparator *	compare
CCC_Allocator *	allocate
void *	context

Field Documentation

allocate

CCC_Allocator* CCC_Priority_queue::allocate

The allocation function, if any.

compare

CCC_Type_comparator* CCC_Priority_queue::compare

The comparison function to enforce ordering.

context

void* CCC_Priority_queue::context

Auxiliary data, if any.

count

size_t CCC_Priority_queue::count

Quantity of nodes stored in heap for O(1) reporting.

order

CCC_Order CCC_Priority_queue::order

The order of this heap, CCC_ORDER_LESSER (min) or CCC_ORDER_GREATER (max).

root

struct CCC_Priority_queue_node* CCC_Priority_queue::root

The node at the root of the heap. No parent.

sizeof_type

size_t CCC_Priority_queue::sizeof_type

The size of the type we are intruding upon.

type_intruder_offset

size_t CCC_Priority_queue::type_intruder_offset

The byte offset of the intrusive node in user type.

---

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

• ccc/private/private_priority_queue.h