Tree - Heap Data Structure

1 - About

A heap is a tree data structure constructed from the priority number that needs to satisfy a heap property

The number is called priority because priority queues are often implemented this way

3 - Usage

Heaps are favourite data structures for many applications:

  • heap sort sorting algorithm (The binary heap was introduced by J. W. J. Williams in 1964 for this algo)
  • Selection algorithms (finding the min, max or both of them, median or even any kth element in sub-linear time),
  • graph algorithms such as Dijkstra's algorithm

4 - Property

A heap can satisfy one of this two property:

4.1 - Min Heap

In a min heap:

  • the root store the lowest priority element
  • the priority value of a parent node is less than or equal to the priority value of child

4.2 - Max heap

In a max heap,

  • the root store the highest priority element
  • the priority value of a parent is greater than or equal to the priority value of child

Example: a binary max heap (By Ermishin - Own work, CC BY-SA 3.0)

5 - Characteristic

6 - Documentation / Reference


Data Science
Data Analysis
Statistics
Data Science
Linear Algebra Mathematics
Trigonometry

Powered by ComboStrap