Lecture 5/13: Lecture 17 Q&A
Lecture 17 Questions and Answers (Exported from Zoom Q&A log)
Q: Why is the seconds annoying? I find it comforting.
A1: Not sure, I always run with seconds on, indication my computer is still ticking (or freezes at time when things went southā¦)
Q: are the elements in these heaps always ints? if not, how else would you determine something is "larger" if it was a vector for example
A1: To store elements in a heap, you need to have some notion of priority for each element ā could be an associated number or some calculated properly (say for a Vector, priority coudl be the number of elements)
Q: are the numbers meant to represent prioryity, or do the actual values have to be stacked like this?
A1: In this example, the element and the priority is one and the same
Q: can each parent only have 2 children maximum?
A1: Yes, we are working only with binary heaps, which means a maimum of 2 children
Q: Are those two heaps considered different?
A1: The two heaps on screen right now? yes, they are different
Q: less than ?
A1: Not sure of the context for this question., sorry, can you explain?
Q: So the entire thing is not a min heap if one branch fails, or just that part is not one?
A1: yes, if any branch violates the property then the whole thing is not a min heap
Q: Is it just one or the other, or could something be both a min and max heap, like starts out min then becomes max?
A1: Arrangement is either a min heap or a max heap. It is sort of analagous to keeping an array in sorted order versus one in reserve sorted order
Q: what exactly is the definition of āheapā?
A1: Heap is a complete binary tree where each parent and children obey the heap ordering property (ie parent is higher priority than either child)
Q: should the rest of the heap be filled in?
A1: IN this example, there are on 9 entries in this heap
Q: Is that different from the heap we talked about in stack vs. heap?
A1: Yes, it is different use of same word.
Q: do we get an error if we find the parent of the root of the heap
A1: The root is at index 1, if you divide by 2, you get index 0, where is unused in our array, but accessing it would technically not be a runtime error (but it is logical error)
Q: what if the parent and child have the same valueā¦is that considered not a min or max heap?
A1: This is fine, parent priority has to be higher or equal priority, equal is ok
Q: Are heaps necessarily binary? Or are there such thing as non-binary heaps?
A1: By heap, we refer to binary heap, but there are other variations with different arrangements
Q: is this a stanford library or standard
A1: binary heap is a classic data structure, exists across language/libraries.
A2: The class he is going to build is called PriorityQueue, which is the Stanford Library name for the ADT
Q: What's the point of peek() if we are returning a constant everytime? couldn't we just return heap[1]?
A1: That is what peek does, yes!
Q: im sorry i dont quite understand ā are peek() and return heap[1] the same? do either actually remove something? how can it be O(1) if it does remove something and all indexes need to shift?
A1: The peek() function is an operation on a heap that returns the value of root element
Q: Is there a reason the methods use the word "queue"? Like is it FIFO somehow?
A1: Yes! This data structure is often called a PriorityQueue, where elements are dequeued in order of priority
Q: So you can use either peek or heap[1]?
A1: Typically the member variables of the class would be marked private so clients will not be able to directly access heap array, and have to use peek() operation
Q: does a heap know that it is a heap, or is it on us to notice when we make a placement error?
A1: The heap is stored in an ordinary array, it is up to the code to be sure that elements are placed into the array in such a way to maintain the heap ordering property
Q: Since this is just an array, does this mean that weād be able to add all of these āfalseā values in theory, but that would violate our purpose of heaps, or is there an actual structure called heaps that would call an error?
A1: The heap is stored in an ordinary array, it is up to the code to be sure that elements are placed into the array in such a way to maintain the heap ordering property
Q: how can we make Qt know that we are building a max-heap or min-heap?
A1: Not sure what you mean. Qt is just a compiler. It does not enforce how you arrange elements within an array, that is going to happen in your code
Q: why is it better to implement bubble up recursively instead of using a while loop?
A1: It could be either. I would probably write it iteratively myself
Q: do we have to write bubble up or is it already ābuilt inā to heaps?
A1: There is no such thing as ābuilt-inā heap ā needs to be implemented to exist
Q: So each node can have either one or two edges?
A1: Yes, one or two children
Q: How do heaps deal with duplicate entries?
A1: Nothing special, the order is that parent is higher or equal priority, equal is ok, no need to swap
Q: Is it true that if you enqueue stuff in a different order, you'll end up with a different heap?
A1: Yes
Q: In the last case was it still considered a heap since one of the parents had only 1 kid? it then wouldnāt be complete right and therefore isnāt a heap?
A1: a heap is complete if all levels are filled, except for the last level, which may be partially filled from left to right
Q: what happens if you have two elements that are the same (so equal priority)
A1: Nothing special, the order is that parent is higher or equal priority, equal is ok, no need to swap
Q: so the program itself doesn't know whether a heap is a max-heap or min-heap, right? is that character only defined by our code and known by ourselves?
A1: Yes, exactly.
Q: Concerning the lowest level of the heap, do the empty "children" need to be at the end of the array only? Or can we have an empty index, some more values, and then empty all while in the last level?
A1: Any empty slots are always at the end of the array
Q: does this dequeueing process happen automatically or do we manually do this bubble-down technique after dequeueing?
A1: All of the code for enqueue/dequeue, bubble/swap is written by you
Q: What if both children are the same priority?
A1: you can arbitrarily pick either one
Q: what is the base case for the recursion when we do bubbling? do we have a function like isBalanced or isHeap or something
A1: Base case is that you stop when the value has arrived at its final location (up or down)
Q: why is it log n
A1: Each level of the tree divides the remaining nodes in half, the number of levels is bounded by the nubmer of times you can divide N by 2, which is log base 2 of N
Q: So, is the purpose of these two algorithms to find the right place to put a value that you want to add to the heap?
A1: Yes, exactly!
Q: how can we tell its Big O is log(n)? I don't quite see the logic
A1: Each level of the tree divides the remaining nodes in half, the number of levels is bounded by the nubmer of times you can divide N by 2, which is log base 2 of N
Q: why bubbling down is logn? Isnāt the childern 2 times more than the parent?
A1: Each level of the tree divides the remaining nodes in half, the number of levels is bounded by the nubmer of times you can divide N by 2, which is log base 2 of N
Q: Couldn't you also achieve a priority queue with a sorted array?
A1: Yes, but insert in sorted order is O(N)
Q: what about normal queues?
A1: Can get frontmost in O(1) but since queues are FIFO, that is access to oldest element in queue, not highest priority
Q: What does he mean to insert an element with a key?
A1: For example, the entry to enqueue is student name, and the priority is specified as additional argument
Q: can the key k be a pointer to some diff value (not int) and in that sense our heap is "storing" other value types?
A1: Definitely! The collection ADTs are usually specified as a template type, which allows client to choose what element type is appropriate for their needs
Q: or how does the key work?
A1: For this example, the key is priority (usually an integer)
Q: Sets and maps also itereate in sorted order, right? So what's the benefit of heaps over one of those?
A1: Heaps are actually more weakly ordered that sorted set/map, their speciality is for accessing the highest priority element. This is a use case for certain applications, triange in waiting room, scheduling jobs in an OS, etc.
Q: why was the highest priority B and not A
A1: Sorry, I have lost the context for this question. The priority was a number, the letter was the element
Q: why peekPriorityās output is an integer while others are alphabets?
A1: peekPriority gives the priority of the highest priority elemtn, which is represented as an integer. the other methods enqueue and dequeue operate on elements themselves, which are letters in this case (but in general can be anything)
Q: So in this instance is the priority queue and the binary heap the same thing ?
A1: almost āĀ the priority queue is a data structure that supports all the listed operations and it is built on top of a binary heap (same way that a vector is built on top of an array like we saw on Monday)
Q: can you please re explain the first bubble sort where you inserted the number 9
A1: live answered
Q: Oh i see ok thank you
A1: live answered