Skip to content

Instantly share code, notes, and snippets.

@vivekkr12

vivekkr12/algo_notes.md

Last active January 7, 2020 21:08
Show Gist options
  • Save vivekkr12/10d7ed015ae88901a0204a7ca80d8991 to your computer and use it in GitHub Desktop.
Save vivekkr12/10d7ed015ae88901a0204a7ca80d8991 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
algo_notes.md

Notes for Algorithms Revision

Dynamic Programming

  • Split the problem into sub problems such that their solutions can be used to construct the solution of the complete probelm
  • Mostly used in optimization problems like max sub array sum, stock buy sell etc.
  • Can't be used when there are more than one solution

Heaps

  • A binary heap is a binary tree i.e. each node must have two children. The tree is filled sequentially i.e. only the nodes at the end are allowed to have less than 2 children
  • Heaps satifies the heap invariant i.e. child nodes <= parent node (max heap) or child nodes >= parent nodes (min heap)
  • In max heap, the root is the max element
  • In min heap, the root is the min element
  • Trees must not have cycle in a heap
  • Use max heap for in place heap sort
  • Use min heap to find the Kth largest elements or K largest elements
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment