Data structures heaps and priority queues flashcards
Flashcards covering essential concepts of heaps and priority queues in computer science, ideal for college-level understanding and exam preparation.
Quiz(24 questions)
1. What is the primary characteristic of a max-heap?
Terms in this Study Set(24)
Flashcards 1(12)
What is a heap?
A binary tree satisfying the heap property: 1) Max-Heap: parent >= children, 2) Min-Heap: parent <= children.
True or False: A max-heap allows efficient access to the maximum element.
True - The maximum element is always at the root, allowing O(1) access.
Fill in the blank: The time complexity to insert an element in a heap is ____.
O(log n) - due to the tree's height.
Compare heap and array for priority queues.
Heap: dynamic, O(log n) for insert/delete. Array: static, O(n) for insert, O(1) for delete max.
What operation removes the highest priority element?
Extract-Max from a max-heap - re-heapify afterward; O(log n) complexity.
When is a priority queue useful?
Task scheduling, like CPU scheduling or bandwidth management.
What is a min-heap?
A binary tree where the parent is less than or equal to its children, allowing efficient minimum access.
Cause → Effect: If you add an element to a heap, then ____.
The heap property may need to be restored (heapify up).
What is the time complexity to build a heap from an unsorted array?
O(n) - using the bottom-up approach (heapify).
True or False: Heaps can be implemented using linked lists.
False - Heaps are typically implemented using arrays for efficient index-based access.
Give an example of a real-life priority queue.
Emergency room triage prioritizing patients based on severity.
Define the 'heapify' process.
Rearranging elements to maintain the heap property after insertion or deletion.
Flashcards 2(12)
What is the time complexity for inserting in a binary heap?
Average and worst case: O(log n) - Due to the need to maintain the heap property.
True or False: A max heap allows duplicate values.
True - Duplicate values can exist, but they do not affect the heap structure.
Compare max heap and min heap.
Max Heap: Parent nodes ≥ child nodes. Min Heap: Parent nodes ≤ child nodes.
Fill in the blank: In a priority queue, the element with the highest priority is _____ .
removed first - Priority queues serve elements based on priority, not order.
What operation is performed to remove the root of a heap?
- Swap root with last element. - Remove last element. - Heapify down from new root.
When is a heap generally preferred over other data structures?
When frequent access to the highest or lowest priority element is needed.
What is the space complexity of a binary heap?
O(n) - Space is used to store the n elements in the heap.
How do heaps maintain their structure during insertion?
By 'bubbling up' the newly added element to maintain the heap property.
List one common use of priority queues.
Task scheduling - Prioritize tasks based on urgency.
What is the worst-case time complexity for deleting from a binary heap?
O(log n) - Requires re-heapifying after removing the root.
Cause → Effect: Deleting the root of a max heap causes _____ .
The next largest element to become the new root.
What property does a binary heap satisfy?
Complete binary tree - Every level is fully filled except possibly the last.
Questions in this Study Set(24)
1. What is the primary characteristic of a max-heap?
2. What is the average time complexity for removing the root from a binary heap?
3. Which operation is used to access the minimum element in a min-heap?
4. True or False: A min heap allows duplicate values to exist.
5. What is the time complexity of deleting the highest priority element from a max-heap?
6. In a priority queue, how is the priority typically determined?
7. Which data structure is NOT suitable for implementing a priority queue?
8. What happens to the structure of a binary heap after inserting an element?
9. Fill in the blank: The process used to restore the heap property after inserting an element is called ____.
10. Which of the following is NOT a characteristic of binary heaps?
11. In which scenario would a priority queue be most useful?
12. What type of tree structure does a binary heap represent?
13. True or False: The time complexity to build a heap from an unsorted array is O(n).
14. What is the space complexity of a binary heap storing n elements?
15. What is the main disadvantage of using an array for a priority queue?
16. In which scenario is a max heap typically favored?
17. Which statement is true regarding the heapify process?
18. What is the result of removing the root from a max heap?
19. Which of the following accurately describes a min-heap?
20. What operation is typically used to restore the heap property after removing the root?
21. What happens if you remove the highest priority element from a max-heap?
22. What is one common application of priority queues?
23. True or False: Heaps can be efficiently implemented with arrays.
24. How do heaps differ from other data structures like arrays or linked lists?
Related Study Sets
Informatyka studia – Algorytmy i struktury danych
Hashing Kollisionsauflösung Prüfungsfragen
Minimaler Spannbaum Kruskal Prim Klausurvorbereitung
AVL-Bäume Rotationen Klausurvorbereitung
Sortieren einfach erklärt Karteikarten
Breitensuche und Tiefensuche Definitionen
Heap und Heapsort Karteikarten
Mergesort und Quicksort Laufzeit Definitionen
Create Your Own Study Set
Upload a PDF, paste your notes, or describe a topic – AI generates flashcards, quizzes and more in seconds.
