Heaps

Textbook Reference: Chapters 7.8-7.10

Summary of Worst Case data structure runtimes

data structure	insert	insert_list	find	find_smallest	remove	remove_min
list (unsorted)	ϴ(1)	ϴ(n log n)	ϴ(n)	ϴ(n)	ϴ(n)	ϴ(n)
list (sorted)	ϴ(n)	ϴ(n log n)	ϴ(log n)	ϴ(log n)	ϴ(n)	ϴ(n)
BST (ave)	ϴ(log n)	ϴ(n log n)	ϴ(log n)	ϴ(log n)	ϴ(log n)	ϴ(log n)
BST (worst)	ϴ(n)	ϴ(n^2)	ϴ(n)	ϴ(n)	ϴ(n)	ϴ(n)
AVLTree	ϴ(log n)	ϴ(n log n)	ϴ(log n)	ϴ(log n)	ϴ(log n)	ϴ(log n)
Heap	ϴ(log n)	ϴ(n log n)	---	ϴ(1)	---	ϴ(log n)
Fibonacci Heap	ϴ(1)	ϴ(n)	---	ϴ(1)	---	ϴ(log n)

Note:

1. For a sorted list, bulk insert is equivalent to sorting a list; find element uses binary search
2. You should be able to construct examples that generate the best/worst case runtimes
3. We won't discuss the Fibonacci Heap implementation in class, but I want you to understand that the Heap we will discuss is not optimal

Heap

1. A heap is a binary tree that is:

   1. Complete

      1. Every level except (possibly) the last level is full (i.e. every node has both a left and right child)
      2. The last level is filled in a left-to-right order

   2. Heap property:

      1. Min-heap: The value of any node is smaller than the value of its children
      2. Max-heap: The value of any node is larger than the value of its children

2. Operations:

   1. insert

   2. remove_min

   3. find_smallest

   4. (you should be annoyed that I've used min in some functions and smallest in others)

   5. pseudocode is provided in the comments of the containers/Heap.py file

Homework

IMPORTANT: You should think of this homework like a "take home test" with no time limit. Therefore, this homework has a modified collaboration policy: You may not work with another human on this assignment in any way. For example, you may not: 1. Discuss the code with another student. 2. Look at another student's code. 3. Visit the QCL for help with this assignment. 4. Post issues to github related to the assignment. If you do have a question, you can ask me in office hours or over email. I may or may not be able to answer your question. I will answer questions related to git or the heap at a high level, but I will not answer questions related to python.

1. Recall that git is a protocol, and not a webpage. This means that git can be used with many different websites, or no website at all. One popular alternative to GitHub is called GitLab, and your next homework assignment is hosted there.

   The repo located at https://gitlab.com/mikeizbicki/random-project contains a branch called heap. This repo is a fork of the https://github.com/mikeizbicki/containers repo; that means it contains all the same code, plus more. GitHub "forks" are a special type of fork where both versions of code are hosted on github, but in general a fork is any copy of a code repo.

   HISTORICAL NOTE: Linus Torvalds created git in 2005 to manage the Linux kernel source code. (See detailed history on wikipedia.) GitHub was founded 3 years later in 2008, and was definitely not the first website to host repos for open source software. SourceForge, for example, has been hosting SVN repos since 1999. (SVN is an alternative VCS to git.) "Fork" is a term that's been around in the open source community since the very beginning, and is not something unique to GitHub. Anytime you take someone else's open source code and modify it in any way, you've "forked" that code. Typically, we reserve this word for when two projects share the same initial code, but then do not merge each other's downstream commits for whatever reason. See wikipedia for details.

   Recall that Microsoft was viewed as the "evil tech giant" by the open source world in the 90s and 00s because they used shady legal tactics to suppress open source software. Today's tech giants like Google/Facebook are better at supporting open source software, but they still do not support open standards (see Google's AMP and Floc systems, and Facebook's internet.org and lobbying efforts ). This is the fundamental reason that many programmers view these tech giants as "evil" today.

   Microsoft purchased GitHub in 2018 as part of a long-standing plan to ingratiate itself with the open source community. As part of that plan, they offered unlimited use of GitHub Actions as a free service for any open source developer. That's why we're using GitHub Actions in this class instead of one of the other alternatives. Last year, however, we used Travis CI, and when GitHub Actions eventually becomes non-free, I'll switch the class over to using a different free service. The advantage of an open protocol system like git is there is no lock-in, so you can always switch to a better service easily.

2. You should:

   1. Add a new remote to your local repo on the lambda server that points to the gitlab repo.

   2. Create and checkout a branch in your homework repo called heap. heap should be based off of the bst branch and not the master or avltree branches.

      IMPORTANT: The code in your heap branch will require that you have access to your BinaryTree class, and that BinaryTree passes all the test cases. You do not need to have a working BST or AVLTree class for this assignment.

   3. Pull the contents of the gitlab repo's heap branch into your branch.

   4. Fix the file containers/Heap.py so that all the test cases pass.

   1. Update your README.md file to include a build status icon for the Heap.

   2. All your work must be done in the heap branch, and you must not merge your work into the master, bst, avltree branches. If you merge your work into any of these branches, you will receive a -8 point penalty on the assignment.

3. Submit the link to your heap branch on github to sakai. If you submit a link to any other branch instead, you will receive a -8 point penalty on the assignment.