Practice TestTake a test on your terms and definitions
Spaced RepetitionScientifically backed study method
Matching GameHow quick can you match all your cards?
FlashcardsStudy terms and definitions
1 / 25
There's no tags or description
Looks like no one added any tags here yet for you.
26 Terms
1
What is a binary heap?
A binary heap is a type of priority queue that is represented as an almost complete binary tree, where the parent node is always less than or equal to its children.
New cards
2
What is the heap property?
The heap property states that for any given node, its value must be less than or equal to the values of its children.
New cards
3
How are elements stored in a binary heap?
Elements are stored in an array using level order encoding, where the tree structure is represented linearly.
New cards
4
Why is it important for a binary heap to be almost complete?
Being almost complete allows for efficient storage in an array and ensures that the tree remains balanced.
New cards
5
What is the significance of the height of a binary heap?
The height of binary heap is (log n), which determines the time complexity for operations like insert and remove.
New cards
6
What are the main operations supported by priority queue?
The main operations are INSERT and REMOVE MIN (or remove max).
New cards
7
How is the minimum element accessed in a binary heap?
The minimum element is always at the root of the binary heap.
New cards
8
What is the time complexity for the insert operation in a binary heap?
The insert operation runs in O(log n) time.
New cards
9
What happens when you remove the minimum element from a binary heap?
The root element (minimum) is swapped with the last element in the array, and then sift down is called to restore the heap property.
New cards
10
Can a binary heap efficiently find an arbitrary element?
No, binary heaps do not support efficient methods for finding arbitrary elements once they are inserted.
New cards
11
How do you decrease the key of an element in a binary heap?
Decreasing the key makes the element smaller, which may violate the heap property, requiring a sift up operation.
New cards
12
What is the time complexity of building a heap using the insert method in the worst case?
O(n log n)
New cards
13
What is the time complexity for building a heap using the bottom-up method?
O(n), in worst case which is linear time.
New cards
14
What is the significance of the height of an element in binary heap?
The height of an element determines how much work is needed to sift it down or up, affecting the overall time complexity of heap operations.
New cards
15
What is the purpose of the sift up operations?
The sift up operation fixes violations of the heap property by moving an element up the tree until the heap property is restored.
New cards
16
What does the sift down operation do?
The sift down operation moves an element down the tree to restore the heap property by swapping it with its smallest child.
New cards
17
What is the sift-up operation?
The sift-up operation is used to maintain the heap property by moving an element up the tree until the heap property is restored.
New cards
18
What is the sift-down operation?
The sift-down operation is used to maintain the heap property by moving an element down the tree until the heap property is restored.
New cards
19
What is the relationship between binary heaps and sorting?
Binary heaps can be used for sorting by repeatedly inserting elements and then removing the minimum.
New cards
20
What is the running time of the heap sort algorithm?
The running time of the heap sort algorithm is O(n log n), as it involves n calls to removeMin after building the heap.
New cards
21
How does heap sort differ from merge sort?
Heap sort runs in-place and does not require additional storage, while merge sort requires additional space for merging.
New cards
22
What is a key advantage of heap sort over quick sort?
Heap sort is deterministic O(n log n) algorithm, while quick sort can have a non-deterministic performance depending on the pivot selection.
New cards
23
What happens when you repeatedly call removeMin on a binary heap?
Repeatedly calling removeMin will result in the elements being sorted in reverse order, as each minimum is swapped to the end of the array.
New cards
24
What are some favorable characteristics of heaps?
Heaps are efficient for priority queue operations, have a predictable time complexity, can be implemented in an array without pointers.
New cards
25
What is the difference between a min-heap and a max-heap?
In min-heap, the parent node is less than or equal to its child nodes, while in a max-heap, the parent node is greater than or equal to its child nodes.
New cards
26
Why is the heap data structure useful in algorithmic applications?
Heaps are useful for implementing priority queues, sorting algorithms, and for efficiently finding the min or max element.
Studied by 0 people
