Heap

a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. The node at the “top” of the heap (with no parents) is called the root node.

max heap: children are smaller or equal to parents

best way to implement a priority queue. In addition, peek (in this context often called find-max or find-min), which returns the highest-priority element but does not modify the queue, is very frequently implemented, and nearly always executes in O(1) time. Best implementation of a priority queue is usually a heap. So they are called heaps frequently

A heap is not a sorted structure and can be regarded as partially ordered.

A heap is a useful data structure when you need to remove or peek the object with the highest (or lowest) priority.

usually implemented as an array

you can write a method to turn an array into a heap by rearranging the items

Binary heaps are common

  • normally implemented as an array
  • parent keys are bigger than children
  • all rows need to be compete except for last row
  • they can contain duplicates
  • slow at traversal and search
  • fast insert and delete
  • fast at sorting - heap sort

remove

  1. take the very last item in the array and replace the root you are removing
  2. then switch it with the larger child
  3. then switch it with the larger child
  4. keep doing that until its in the right position

insert

  1. add inserted node to the very end of the array
  2. replace parent if larger
  3. repeat until its in the right place

heapsort

just pop off the root and put it at the end of the array over and over until the heap is empty

populates top to bottom left to right

when removing the root element, replace it with the last element at the bottom and move it to thr right spot

if storing in an array you can get left child i*2+1, right child i*2+2