Rocket Academy Bootcamp
  • 🚀Welcome to Bootcamp!
  • 🛠️Logistics
    • Course Schedules
    • Course Methodology
    • Required Software
    • LinkedIn Education Badge
  • 📚General Reference
    • Naming, Casing, and Commenting Conventions
    • VS Code Tips
    • Recommended Resources
  • 🪨0: Foundations
    • 0.1: Command Line
    • 0.2: Git
      • 0.2.1: Branches
    • 0.3: GitHub
      • 0.3.1: Pull Requests
    • 0.4: JavaScript
      • 0.4.1: ES6
      • 0.4.2: Common Syntax
      • 0.4.3: Reference vs Value
      • 0.4.4: Classes
      • 0.4.5: Destructuring and Spread Operator
      • 0.4.6: Promises
        • 0.4.6.1: Async Await
    • 0.5: Node.js
      • 0.5.1: Node Modules
      • 0.5.2: NPM
      • 0.5.3: Nodemon
  • 🖼️1: Frontend
    • 1.1: HTML
    • 1.2: CSS
      • 1.2.1: Layout
    • 1.3: React
      • Styling in ReactJs
      • Using Styling Libraries with React
      • React Deployment
    • 1.E: Exercises
      • 1.E.1: Recipe Site
      • 1.E.2: Portfolio Page
      • 1.E.3: World Clock
      • 1.E.4: High Card
      • 1.E.5: Guess The Word
    • 1.P: Frontend App
  • 🏭2: Full Stack
    • 2.1: Internet 101
      • 2.1.1: Chrome DevTools Network Panel
      • 2.1.2: HTTP Requests and Responses
    • 2.2: Advanced React
      • 2.2.1: AJAX
      • 2.2.2: React Router
      • 2.2.3: useContext
      • 2.2.4: useReducer
      • 2.2.5: Environmental Variables
      • 2.2.6: React useMemo - useCallback
    • 2.3: Firebase
      • 2.3.1: Firebase Realtime Database
      • 2.3.2: Firebase Storage
      • 2.3.3: Firebase Authentication
      • 2.3.4: Firebase Hosting
      • 2.3.5: Firebase Techniques
    • 2.E: Exercises
      • 2.E.1: Weather App
      • 2.E.2: Instagram Chat
      • 2.E.3: Instagram Posts
      • 2.E.4: Instagram Auth
      • 2.E.5: Instagram Routes
    • 2.P: Full-Stack App (Firebase)
  • 🤖3: Backend
    • 3.1: Express.js
      • 3.1.1 : MVC
    • 3.2: SQL
      • 3.2.1: SQL 1-M Relationships
      • 3.2.2: SQL M-M Relationships
      • 3.2.3: SQL Schema Design
      • 3.2.4: Advanced SQL Concepts
      • 3.2.5: SQL - Express
      • 3.2.6: DBeaver
    • 3.3: Sequelize
      • 3.3.1: Sequelize One-To-Many (1-M) Relationships
      • 3.3.2: Sequelize Many-To-Many (M-M) Relationships
      • 3.3.3: Advanced Sequelize Concepts
      • 3.3.4 Database Design
    • 3.4: Authentication
      • 3.4.1: JWT App
    • 3.5: Application Deployment
    • 3.E: Exercises
      • 3.E.1: Bigfoot JSON
      • 3.E.2: Bigfoot SQL
      • 3.E.3: Bigfoot SQL 1-M
      • 3.E.4: Bigfoot SQL M-M
      • 3.E.5: Carousell Schema Design
      • 3.E.6: Carousell Auth
    • 3.P: Full-Stack App (Express)
  • 🏞️4: Capstone
    • 4.1: Testing
      • 4.1.1: Frontend React Testing
      • 4.1.2: Backend Expressjs Testing
    • 4.2: Continuous Integration
      • 4.2.1 Continuous Deployment (Fly.io)
      • 4.2.2: Circle Ci
    • 4.3: TypeScript
    • 4.4: Security
    • 4.5: ChatGPT for SWE
    • 4.6: Soft Skills for SWE
    • 4.P: Capstone
  • 🧮Algorithms
    • A.1: Data Structures
      • A.1.1: Arrays
        • A.1.1.1: Binary Search
        • A.1.1.2: Sliding Windows
      • A.1.2: Hash Tables
      • A.1.3: Stacks
      • A.1.4: Queues
      • A.1.5: Linked Lists
      • A.1.6: Trees
      • A.1.7: Graphs
      • A.1.8: Heaps
    • A.2: Complexity Analysis
    • A.3: Object-Oriented Programming
    • A.4: Recursion
    • A.5: Dynamic Programming
    • A.6: Bit Manipulation
    • A.7: Python
  • 💼Interview Prep
    • IP.1: Job Application Strategy
    • IP.2: Resume
    • IP.3: Portfolio
Powered by GitBook
On this page
  • Learning Objectives
  • Introduction
  • How Heaps Work
  • Exercises
  • Tips
  • Pre-Class
  • Part 1
  • Part 2
  • Part 3
  • More Comfortable
  • Additional Resources
  1. Algorithms
  2. A.1: Data Structures

A.1.8: Heaps

PreviousA.1.7: GraphsNextA.2: Complexity Analysis

Learning Objectives

  1. Heaps are a data structure that enables us to efficiently track the minimum or maximum in a collection of elements, even as that collection changes.

  2. Heaps are commonly used to implement priority queues for use cases such as hospital queues, bank queues and process queues in operating systems.

  3. JavaScript does not have a built-in heap implementation and building heaps from scratch using arrays is relatively complex. Because heaps are less commonly seen in interviews, Rocket recommends we master other data structures before focusing on heaps, and use Python and its built-in heapq library when we are ready to solve heap problems.

Introduction

Heaps are a data structure that enables us to efficiently track the minimum ("min heap") or maximum ("max heap") in a collection of elements, even as that collection changes. Heaps are commonly used to implement "priority queues" for use cases such as hospital queues, bank queues and process queues in operating systems. In these scenarios, heaps enable us to determine which person/element should be at the front of the queue based on factors in addition to insertion order such as severity or importance.

The beauty of heaps is that they enable us to extract the minimum (in a min heap) or maximum (in a max heap) value in O(1) time, while inserting new values into a heap takes O(logn) time. This is more efficient than adding a new element in sorted order to a sorted array, which would take O(n) time. Heaps are able to do this by utilising properties of trees, where heap elements are only partially sorted and not completely sorted like they would be in a sorted array.

How Heaps Work

The following video explains what heaps look like in theory and the fundamental properties of heaps that enable heaps to maintain O(1) access to the min or a max element efficiently. The video uses a max heap as an example, but the same properties apply to min heaps except with the order reversed (smaller numbers on top).

The following video explains how heaps maintain O(1) access to the min or max element when the previous min or max element is removed. Again the video uses a max heap as an example but the same theory applies to min heaps, except with order reversed.

The above videos may not have mentioned, but notice the time complexity of adding or removing an element from the heap is O(logn) because we only perform element swaps down a single path of the heap tree, through O(logn) levels, where n is the number of elements in the heap.

Now that we've learnt the theory, you may be wondering how to implement heaps in practice. The following video explains how to efficiently represent the heap data structure in code using an array.

Please review Rocket's Python submodule before working on heap algorithm exercises with heapq.

Exercises

Tips

  1. Python's heapq data structure is a min heap by default. To use heapq as a max heap with numerical values, multiply every number you insert by -1 on push and pop.

  2. We may wish to sort elements by certain numerical values in a heap, but store associated payloads along with those numerical values. In these situations we can insert tuples (e.g. (x, y)) into our heap, where x is the value to sort by and y is the associated payload. For example, in the K Closest Points to Origin problem below, we could store (dist_to_origin, coordinates) elements in our heap.

  3. A common pattern when solving problems asking for the "max K elements" of anything is to use the reverse kind of heap and maintain the heap size as K. For example, if the problem is asking for "max K elements", we can keep a min heap of size K that stores the max K elements seen so far. Keeping a min heap allows us to find the minimum of the max K elements in constant time, saving us from pushing and popping to our heap if the new element is not within the max K elements so far.

    1. We can do heap[0] to quickly peek at the min element in a min heap or the max element in a max heap.

    2. Conversely, if the problem asks for "min K elements" we can use a max heap of size K.

  4. Heaps are not always necessary. Given a static input list, it may be faster to sort the input list and access the Kth element instead of using a heap. Heaps are most useful when we may not have the full input up front.

Pre-Class

Part 1

    1. Hint: What's the most efficient way to get the Kth largest element in a heap of size K? Would we use a min-heap or max-heap? Review tips above before starting.

Part 2

Part 3

More Comfortable

Additional Resources

JavaScript does not have a built-in heap data type, and implementing heaps from scratch is relatively complex. for a JavaScript implementation of heaps.

Rocket recommends we focus on mastering other data structures and algorithms first before attempting heap problems. When ready to solve heap problems, Rocket recommends we use Python and its built-in library, where heappush and heappop (equivalent to insert and remove respectively in JS code example above) are implemented for us.

Please use Python3 and the to use heaps in code.

Last Stone Weight ()

(Python)

(Python)

Kth Largest Element in Array ()

K Closest Points to Origin ()

The K Weakest Rows in a Matrix ()

Top K Frequent Words ()

Hint: Creating a heap of n elements is an . Hence building and maintaining a heap of frequencies and associated words of size K is more efficient (O(n)) than sorting all frequencies of up to n distinct words (O(nlogn)).

(same concepts as above)

introducing heaps

🧮
Here is sample code
heapq
Python heapq library
LeetCode
Rocket Solution code
Rocket Solution video
LeetCode
LeetCode
LeetCode
LeetCode
O(n) operation
Alternative video explanation of heaps by Back to Back SWE
Rocket's FTBC3's class video
Introduction to heaps and how heaps maintain O(1) access to min or max element when new element added
How to represent and use heaps in code with arrays
How heaps maintain O(1) access to min or max element after removal of previous min or max element