Data Structures Flashcards
Focus on specific data structures and their properties, operations, applications, and complexities.
What is a Heap?
A Heap is a special tree-based data structure. It’s a complete binary tree and satisfies the heap property: in a max heap, every parent node is greater than or equal to its children; in a min heap, every parent node is less than or equal to its children.
Describe the two types of Heaps.
Max Heap: The key of the parent is greater than or equal to the keys of its children.
Min Heap: The key of the parent is less than or equal to the keys of its children.
What is the time complexity of inserting an element into a Heap?
The time complexity of inserting an element into a Heap is O(log n), where n is the number of elements in the Heap.
What are some common applications of Heaps?
Heaps are used in implementing priority queues, for efficient minimum or maximum element retrieval, in heap sort, and in graph algorithms like Dijkstra’s and Prim’s algorithm.
Explain how a Heap is represented in memory.
A Heap is usually represented as an array. The root element will be at index 0. For any index i, its children are at indices 2i + 1 and 2i + 2, and its parent is at index (i-1)/2.
What does heapify(iterable) do in Python’s heapq module?
Purpose: Transforms the iterable into a heap in-place.
Description: Rearranges the elements of the iterable into heap order.
Time Complexity: O(n).
Usage Example: heapq.heapify(my_heap)
Describe heappush(heap, elem) in Python’s heapq module.
Purpose: Adds an element to the heap.
Description: Maintains the heap invariant after adding the element.
Time Complexity: O(log n).
Usage Example: heapq.heappush(my_heap, item)
What is the function of heappop(heap) in Python’s heapq module?
Purpose: Pops and returns the smallest element from the heap.
Description: Removes the smallest element, maintaining the heap structure.
Time Complexity: O(log n).
Usage Example: smallest = heapq.heappop(my_heap)
Explain heappushpop(heap, elem) in Python’s heapq module.
Purpose: Pushes a new element and then pops the smallest element from the heap.
Description: More efficient than separately calling heappush followed by heappop.
Time Complexity: O(log n).
Usage Example: item = heapq.heappushpop(my_heap, item)
What type of heap does Python’s heapq module implement by default?
The heapq module implements a min heap.
How do you create a max heap using Python’s heapq module?
Negate the values before inserting them into the heap and negate again when extracting. For instance, use heappush(heap, -value) to insert and -heappop(heap) to extract the max.
Are elements in a heap sorted beyond the root?
No, heaps are partially ordered. While the root is the smallest (min heap) or largest (max heap), the rest of the elements are not fully sorted.
When is using a Min-Heap most effective for finding the kth Largest Element?
Min-Heap is effective when k is large, particularly closer to the size of the list.
Process:
* Convert the entire list into a min-heap.
* Pop n - k elements, leaving the kth largest element at the root.
Efficiency:
* The heap size is reduced to exactly k, making each heappop operation O(log n).
* Ideal for scenarios where the kth largest element is towards the end of the sorted list.
When is using a Max-Heap most effective for finding the kth Largest Element?
Max-Heap is more efficient when k is small.
Process:
* Invert the values (negate them) to create a max-heap using Python’s heapq, which inherently supports min-heaps.
* Pop k - 1 elements, leaving the kth largest element at the root.
Efficiency:
* Fewer pop operations are needed for smaller k, each being O(log n).
* Ideal for scenarios where the kth largest element is towards the beginning of the sorted list.
