🍁
Data Structures and Algorithms
  • Introduction
  • Introduction to Algorithms Analysis
    • Growth Rates
    • Big-O, Little-o, Theta, Omega
    • Analysis of Linear Search
    • Analysis of Binary Search
  • Recursion
    • The runtime stack
    • How to Write a Recursive Function
      • Example: the Factorial Function
    • Drawbacks of Recursion and Caution
  • Lists
    • Implementation
    • Linked List
      • Nodes
      • Iterator
      • Template Singly Linked List
      • Doubly Linked List
      • Circular Linked List
  • Stacks
    • Stack Operations
    • Stack Implementations
    • Stack Applications
  • Queue
    • Queue Operations
    • Queue Implementations
    • Queue Applications
  • Tables
    • Simple Table
    • Hash Table
      • Bucketing
      • Chaining
      • Linear Probing
      • Quadratic Probing and Double Hashing
  • Sorting
    • Simple Sorts
      • Bubble Sort
      • Insertion Sort
      • Selection Sort
    • Merge Sort
      • Merge Sort Implementation
    • Quick Sort
    • Heap Sort
      • Binary heap
      • Binary heap basics
      • Insertion into a binary heap
      • Delete from a binary heap
      • Implementation
      • Sorting
  • Introduction to Trees, Binary Search Trees
    • Definitions
    • Tree Implementations
    • Binary Trees
    • Binary Search Trees
      • Insertion
      • Removal
      • Traversals
  • AVL Trees
    • Height Balance
    • Insertion
    • Why it works
  • Red Black Trees
    • Insertion Example
  • 2-3 Trees
  • Graphs
    • Representation
  • Complexity Theory
  • Appendix: Mathematics Review
Powered by GitBook
On this page

Was this helpful?

  1. Sorting
  2. Heap Sort

Binary heap

If you were to implement a priority queue using a regular list, you would essentially have to maintain a sorted list (sorted by priority). This would mean the following:

  1. insertions would be O(n) for sure as you would need to go through an already sorted list trying to find the right place then doing the insertion.

  2. removal is from the "front" of the queue, so depending on how you do your implementation, this can be potentially O(n) also.

This is not very efficient. If we were to create our priority queue in this manner, we would not be able to get a very good run time to our sort.

The interesting thing about a priority queue is that we really don't care where any value other than the one with the highest priority is. We care about that... and we want to be able to find it and remove it quickly but all other values can be essentially anywhere.

A binary heap is a data structure that can help us do this.

PreviousHeap SortNextBinary heap basics

Last updated 5 years ago

Was this helpful?