Love heaps. Thank god this was right after trees. I don't know how I could keep it up much longer. There is a really great heap resource Heaps. Heaps in python are a bit weird. Have to import something from the collections, and we have a lot of methods for heaps such as heapify, heappush, heappop, etc..
- I started and finished heaps. I learned a lot however. I'm just going to spew everything I remember from today. Firstly, heapify in python is O(n) solution, this is better than adding as
- we go through an array or something. Pythons default heapq is a min heap, so to make it a max heap use a -1*(adding value). This reverses the whole tree.
- When a question asks for a k of something. It's most likely a heap problem. However, it is not the most efficient solution for that problem. It will probably be quickselect, but its
really hard to code during an interview, so most people use heaps instead. Maybe learn it and practice it on own time.
- heapq is the library for python. The way to use it is to pass the heap as a parameter, instead of it being a method of the heap. heappush(heap, 45)
- heapq's are the same thing as priority queues because both of them use the same under-the-hood implementation of a list. (parents (i-1)/2, children 2i+1, 2i+2). The whole
practice we did in class.
- I got better at thinking problems through and thinking about the time complexity and space. Not the best, but we are getting there.
- Also, also, we can pass in tuples and lists to heaps. The default function of heapq is to compare values based on the first indexed position. SO a common format with heaps is heappush(heap, [value, idx])
- Heaps can be tricky, but they are just trees and even more, they are a list.
- One thing I did learn is that k and n are very easy to mix up, and affect time complexity a lot
No comments:
Post a Comment