Q: do we have until tomorrow at midnight to finish the diagnostic?
A1: live answered
Q: how do we confirm that our exam went through successfully? as long as we have our submission code, is it OK?
A1: Yes, as long as you have the submission code you are good to go.
Q: since we have until thursday at midnight to do the midterm, can we push the assignment deadline to Friday? I don’t expect to look at the assignment until after the midterm
A1: The grace period extends until Friday, so you can use that time if you need
Q: can priority work sideways on each level as well?
A1: No, the siblings across one level are unordered relative to one another
A2: No, siblings (nodes at the same level) have no relative property applied to them
Q: is there a priority relationship between 8 and 10?
A1: live answered
Q: does the 25 have a higher priority than the 19 even though it’s at a lower row?
A1: live answered
Q: What if a max heap only has one “sibling”? (ex. instead of 5 going to 10 and 8, it only goes to 10)
A1: live answered
A2: live answered
A3: That’s possible (only if the heap has 2 elements in total) but we’ll talk about rules as to how the tree gets filled ina little bit
Q: what happens if the parent and child have the same value?
A1: live answered
A2: Duplicates are allowed – the property for a min heap is just the that parent must not have a larger numericla value than either of its children
Q: How are "children" allocated? - what stops 99 from being under 36 as opposed to 19?
A1: There is a rule — it is coming up!
A2: live answered
A3: It usually depends on insertion order but there are some rules we must follow for insertion – coming soon!
Q: for the bottom level, can you only fill one leaf
A1: Yes, it would have to be the leftmost
A2: (no skipping)
Q: are you only allowed to have two children
A1: Correct
A2: Yes
Q: But if 10 didnt have 2 children, this formula wouldn’t work right?
A1: live answered
Q: does this heap have anything to do with the heap used for dynamic memory?
A1: No, two completely different things!
A2: No, just an overloaded use of term
Q: if we try to access the parent of the root, we would get -1. Would this give us an index out of bounds error?
A1: Yes, it would.
Q: Do the number of children on both sides (after splitting from 5) need to be the same?
A1: no
A2: No, because the bottom left can be partially filled, there can be more children on left than right
Q: Can you use this array structure for complete binary trees that aren’t necessarily min/max heaps?
A1: live answered
A2: Yes, you could. But trees are rarely complete in practice
A3: Yes, its realtively straightforward to store any complete binary tree in this flat manner, but if the tree deviates form being complete at all then you have to use new strategy for storing the tree (we’ll see what next week)
Q: is the parent not included in heapSize?
A1: live answered
A2: It is, the heapSize is the number of valid elements in the array
Q: Are there any benefits to 0-indexed trees over 1-indexed trees? I know for 1-indexed trees, the arithmetic for children and parents is slightly easier.
A1: Not really. The math is somewhat simpler yes, but the risk of indexing mistakes goes way up
A2: 0-indexed storing doesn’t require special case for array operations (like having “dummy” element at index 0)
Q: the peek() method would return the root because it is the smallest right?
A1: Correct, we’ll see that in a second
Q: If you have a complete heap and then dequeue one, won't that mean that one of the numbers will not have a sibling?
A1: Yes, you will have to resolve that (we’ll see how to do so in a second). But also you can only deqeueu from the root of the tree, not nay arbitrary element
Q: are heaps also adts
A1: live answered
A2: Its an organized way of storing information (abstraction) and we’ll see an ADT built on top of a heap soon
Q: Will a heap always have a single root? Or will it ever have more?
A1: live answered
A2: There’s only ever a single root
Q: Start from the beginning of the tree and swap elems before it reaches the largest element smaller than 9
A1: live answered
Q: if you put the element on the bottom and have to move it all the way to the top, wouldn’t that not be as efficient?
A1: If we have to traverse from bottom of tree to top, that’s not so bad though — think about what the height of the tree is bounded by
Q: Is this kind of heap the same as the memory heap we used to for dynamic memory? (Is this what is going on under the hood?)
A1: No, they’re actually two totally distinct concepts.
A2: No, unrelated use of same term
A3: Not exactly
Q: Is this the same if the new element has a sibling?
A1: live answered
A2: There is no requirement about ordering between siblings, the only relationship you have to fix up is between the new element and its parent (and grandparents)
Q: whats the pratical use of a binary heap
A1: live answered
Q: means if 11 had a sibling
A1: live answered
Q: Is this the only possible solution? Do we always try to fill the left-most position that is free?
A1: Yes, we always have to fill that position to maintain the heap as a complete binary tree
Q: Is doing this process of swapping more efficient using recursion rather than iteration?
A1: Either way could work equally well
A2: live answered
A3: Either is good
Q: What’s the syntax of doing these different heap operations?
A1: live answered
A2: live answered
A3: You’ll implement it in this week’s assignment using operations on the underlying array
Q: You can move 13 up to the top, and then rearrange?
A1: live answered
Q: can we enqueue and build the heap from scratch?
A1: live answered
A2: Yes, but that would be more work than necessary
A3: It would be pretty inefficient if we wanted to rebuild the entire heap every time we did a single dequeue operation
A4: This wouldn’t necessarily be the most efficient solution
Q: Move the last element to the beginning of the tree and swap is down
A1: live answered
A2: yup!
Q: Why does “bubble down” not work for insertion?
A1: live answered
A2: It doesn’t guaranatee that the next expty slot in the array will be filled (we have to ensure that by inititally adding element into first empty spot in the array and then bubbling it up to the correct location)
Q: Is this one bubble down or bubble up?
A1: This is bubble down
A2: This is bubble down
Q: How do you check if you’re at the last row of the array to fill? Can you check if children are null?
A1: live answered
A2: You have to check if the child index is lrager than the heap size (number of elements currently in the heap)
Q: does the IEEE paper about random insertion in constant time mean inserting a random integer, or inserting at a random location?
A1: Insertion of random integers – there isn’t really the concept of inserting “at a random location” here
Q: and the reason we have to pick the higher priority child is because that child is able to “parent” its ex-sibling after the swap?
A1: correct!
A2: Yup, exactly.
Q: if you want to turn an array with n elements into one that satisfies the heap property, would it be O(nlogn) since there would be n enqueues and each enqueue would be O(logn)?
A1: A sequence of N enqueues, each at log N is NlogN overall. (but there is a cool approach to turn an array into a heap in one combined algorithm that runs in O(N)
Q: is it possible that when you bubble down, that there might be a gap in the leaves? e.g. there is an element at index 9, none at 10, and something at 11
A1: No, that should not be possible if you follow the algorithm as stated (this would break the heap property of being a complete tree)
Q: just to clarify- heaps can never have a repeat number anywhere in the tree?
A1: live answered
A2: You couokd have duplicates but we don’t really consider that here
Q: What are the advantages of a heap over a Set? Both are O(log n) but Sets also have sorted elements right
A1: live answered
A2: Heaps are organized for extra-efficient access to most urgent priority — O(1)
Q: How is this different than a binary tree?
A1: live answered
Q: Can we loop through the heap?
A1: using array indexes, yes
A2: You can, it’s basically an array under the hood
Q: Would then for-each loop looks just like a normal one in the array?
A1: yes
Q: So a priority queue is a binary heap?
A1: can be implemented as one, yes
A2: A priority queue can be built on top of a heap (it can also be built on top of other data organization techniques, as you’ll see in the assignment)
Q: is {5,A} an array in the queue?
A1: It is an entry in the queue, name is A and priority 5
A2: {5, A} is just a single entity in the array (think of it as a data point with two properties
Q: What are the letters signifying here?
A1: live answered
Q: if you dequeue all elements and print them out as you do, they will be printed out in sorted order right
A1: Yup, exactly!
Q: Would the priority queue change if values are bubbled up or down?
A1: live answered
Q: if there were no null children in the bottom row (i.e. bottom row is completely filled/we had an element in pos 10), how does dequeueing work? which child of the bottom row would you choose for dequeuing?
A1: You would choose the rightmost element (the “last” element)
Q: are sets built on binary heaps
A1: live answered
A2: No, they are backed by a binary search tree
A3: No, sets are built on binary trees, which we’ll see next week!
Q: Are Heaps part of the standard C++ library?
A1: live answered
Q: this heap is a totally diffrent concept compared to the heap in heap/stack?
A1: Yes
Q: What is the difference between the binary tree and binary heap?
A1: live answered
A2: We’ll talk about that next week (we haven’t learned about binary trees)
Q: Is heap something that we can build a priority queue off of (like an array for a stack), or does building a priority queue entail coding the bubbling up and down, etc.
A1: live answered
Q: I don’t understand why we have keys for priority queues now
A1: live answered
Q: in the last example, would you use a map to store the priority and the value?
A1: No, you can use a struct to store two relate dpieces of information (priority and value)
Q: why is the heap that we talked about with dynamic memory called a heap? is there any relation with the heap property stuff here?
A1: Nope, just an overloaded use of same term
Q: Isn't the priority somewhat distorted between siblings?
For example, you can have a heap like:
3
5 100
In this case, wouldn't 100 be dequed before 5?
A1: live answered
A2: No, once 3 is dequeued, 5 would be swapped intot he root location
Q: Wait so for the priority queue, doesn’t it matter more what your value is than what your key is, even if hte key isn’t the smallest?
A1: live answered
Q: what would siblings be in the hospital analogy
A1: live answered
Q: Why does the rightmost column of the priority queue example table not show the element with the highest priority first?
A1: live answered
A2: there’s no real ordering represented there
Q: How do we implement the changePriority() priority queue function?
A1: live answered
Q: what does it mean that priority queues have less fundamental operations?
A1: live answered
A2: Priority queues have 3 main operations (enqueue, dequeue, peek) while other ADTs may have many more fundamental operations
Q: are you allowed to specify your own priority (for example a heap of shortest to longest strings)?
A1: We’re going to use priority of type int in the assignment but you could theoretically make the priority type whatever you want
Q: As I understand it, in general the same priority queue can be represented by multiple distinct heaps. Is this right?
A1: live answered
A2: live answered