Log in from a computer to take this course

You'll need to log in from a computer to start Introduction to Non-linear Data Structures in Swift. But you can practice or keep up your coding streak with the Codecademy Go app. Download the app to get started.

apple storegoogle store
Learn

Wow! Now that we’ve got a handy data structure for our To-Do List, we can get all caught up on the lessons we need to finish! Let’s review some of the things we’ve learned as we’ve built our MinHeap implementation.

To review

  • A heap is a data structure that stores the minimum or maximum values at the top of the heap, depending on how it is set up
  • Each subtree, that is a parent node and its left and right children, will also maintain order. The parent node is always less than its children in a min-heap, or greater than its children in a max-heap.
  • The top of the heap is accessed in O(1), or constant time, since the value at index 0 is always the priority value, no need to search for it.
  • Adding and removing elements from the heap run in O(logN) time, where N is the count of all elements in the heap.
  • Heaps, though visualized as binary trees, are most commonly stored in an array. Parent and child elements are not stored sequentially but rather separated by a factor of 2.
  • When we add an element to a heap, we add it at the end of the array, we then must heapify up until we find a place in the tree that satisfies the heap conditions.
  • Removing an element is not as easy as removing the first element in the array, if we did that we would fracture the tree. Instead, we swap the first and last nodes, remove the last node, and then heapfiy down the tree from the new top node until its placement satisfies the heap conditions.
  • Heaps are integral to the famous Dijkstra’s algorithm, which uses a min-heap to find the shortest path between two nodes of a graph.

Heaps are invaluable data structures to add to a software engineer’s toolkit. While not the right technique to use when sorting a data set, they are excellent when you only need to know the next value you need to work on. Congratulations on expanding your understanding of this structure!

Instructions

Review the code you wrote in the editor to the right, we’ve removed some of the terminal printing just to keep the terminal easy to read. Feel free to add some new tasks, view some, and ultimately finish some of the tasks on your To-Do List!

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?