Knowledge Bank
  • My GitBook
  • Miscellaneous
  • Project
    • Rider and Intellij
    • Code
    • Frontend
      • Condition
      • AddConditionModalDialog
    • Backend
    • e2e
      • fragments
  • JAVASCRIPT
    • Promise
    • Destructuring
    • Spread Syntax and Rest Parameters
    • Typescript
      • Examples of Types
      • React Typescript
    • This
    • Dot Notation vs Bracket Notation
    • Shallow vs Deep Clone
    • New ES Edition
  • C#
    • Project Note
    • Basic
    • Shortcut and Debugging
  • Programming Paradigms
    • SOLID Principles
    • Object Oriented Programming (OOP)
      • Evolution of OOP (Procedural to OOP)
      • Instantiation
      • 4 Pillars of OOP
      • Extra
    • Functional Programming (FP)
      • Idempotent
      • Imperative vs Declarative
      • Immutability
      • High Order Function and Closure
      • Currying
      • Partial Application
      • Memoization and Caching
      • Compose and Pipe
      • Extra
      • Example of FP
    • OOP vs FP
      • Composition vs Inheritance
  • DATA STRUCTURE
    • Big O
    • Data Structure
    • Array
    • Hash Table
    • Linked List
    • Queue and Stack
    • Tree
      • Binary Heap
      • Trie
    • Graph
      • Example of Graph
  • React-Redux
    • MobX
    • Best Practices
  • Algorithms
    • Recursion
      • Examples of Recursion
    • Sorting
    • Searching and Traversal
    • Dynamic Programming
  • REFACTORING
    • Clean Code
      • Formatting
      • Error Handling
      • Concurrency
      • Testing
      • SOLID Principles
      • Classes
      • Objects and Data Structures
      • Variables
      • Functions
    • Code Smells
      • Long Function
      • Duplicate Code
      • Loops
      • Double Negative
      • Christmas Tree Code
      • Complex Condition
      • Primitive Obsession
      • Speculative Generality
      • God Class
      • Long Parameter List
  • Junior to Senior
    • AWS
      • Lambda
    • Session + Authentication
    • Redis
    • Kubernetes
      • Networking
      • Services
      • Deployment
      • Replica Set
      • YAML
      • pod-definition.yml
      • Kubectl
      • Pods
      • Fundamentals
    • Docker
      • Operating System - Extra
      • Dockerfile - Docker Image
      • Docker Storage
      • Docker Network
      • Docker Registry
      • Docker Command
      • Docker Compose
      • Docker Compose - Postgres
    • Security
      • Logging
      • HTTPS, Cross-Site-Scripting (XSS) and Cross-Site-Request-Forgery (CSRF)
      • 3rd Party Library
      • Injection
      • Code Secret, Secure Header, Access Control, Data Management, Authentication
    • CI/CD
    • SPA vs Server-Side Rendering
    • Performance
      • Optimized Code
      • Critical Render Path
      • Backend Optimization
      • Minimized Files and Images
      • Minimized Delivery
  • SECURITY
    • Encryption
    • SSH
  • Command
  • Cheatsheet
    • NPM
    • GIT
  • Writing Template
    • Guide
    • API
    • ChangeLog
    • FAQ
  • Linux
Powered by GitBook
On this page

Was this helpful?

  1. DATA STRUCTURE
  2. Tree

Binary Heap

PreviousTreeNextTrie

Last updated 5 years ago

Was this helpful?

Binary Heap means every child belongs to a parent node that has a greater priority or value. The other name is max heap. Min heap is the opposite where the root node is the smallest. A heap can be used in any algorithm where ordering is important. Thus it is used in Priority Queue.

For lookup, it is O(n), compared to BST where it is O(log N) because Binary Heap is less ordered than a binary search tree. A binary search tree has meaning between left and right, where left is always less than the right. In a binary heap, it doesn't matter, left and right can be any value as long as it's less than the top value. When lookup for value 1, we have to go through every node. So, lookup become 0(n).

The advantage of binary heaps is great at doing comparative operations. If I want a value over 33, we just grab 1st and 2nd level, instead of going all the way down to the nodes. Compared to BST where this operation is O(n).

For insertion, it add value on the tree in order from left to right and then bubbles up. So the best scenario is O(1) and worst O(log N)

The beauty of binary heaps is that they take up the least amount of space possible because it's always left to right insertion. So there's no concept of an unbalanced binary heap.

In general, binary heaps have these advantages:

  1. Better than O(n). Although searching is slower than BST, but we have concept of priority

  2. Priority

  3. Flexible size

  4. Fast insert

The disadvantage is

  1. Slow lookup. But great at finding max or min