Data Structures: Question Set – 09
What is a heap?
A heap is a specific kind of binary tree that fulfils the heap property, which can be either the max-heap property or the min-heap property, depending on the particular heap property being considered. It is often used in the process of implementing a priority queue.
What is the difference between a max-heap and a min-heap?
A max-heap is a type of binary tree in which the value of each node is larger than or equal to the values of its children, and the value that has the highest value is stored in the node that is the tree’s root. A min-heap is a type of binary tree in which the value of each node is either less than or equal to the values of its children, and the value with the lowest value is stored in the node that is directly beneath the root node.
What is the key distinction between a binary search tree and a binary heap?
A binary search tree is a binary tree in which the value of each node is greater than or equal to the values of its left subtree and less than or equal to the values of its right subtree, whereas a binary heap is a complete binary tree in which the value of each node is greater than or equal to (or less than or equal to) the values of its children. A binary heap differs from a binary search tree in that a binary search tree is not a complete binary tree.
The term “self-balancing binary search tree” refers to what exactly?
A binary search tree that automatically adapts its structure to maintain balance and prevent degeneration into a linked list is called a self-balancing binary search tree. This type of binary search tree is also known as a balanced binary search tree. AVL tree and Red-Black tree are two examples of trees that can be used.
What is the advantage of using a priority queue?
When processing needs to be prioritised based on importance or urgency, such as when scheduling tasks or processing network traffic, a priority queue is useful because it enables efficient access to the element with the highest priority. This makes it useful in applications where processing needs to be prioritised.
What is a linked list?
A linked list is a type of data structure that consists of a series of nodes, each of which has a pointer (reference) to the node after it in the sequence.
What distinguishes a linked list from an array?
A linked list is different from an array in that it does not store data in contiguous memory locations. Instead, each node in a linked list is dynamically allocated and can be found anywhere in memory.
What advantages do linked lists have over arrays?
The primary benefit of choosing a linked list over an array is that the former can expand dynamically while the latter has a set size. Linked lists are also more efficient at inserting and removing elements than arrays are.
What kinds of linked lists are there?
Singly linked lists, double linked lists, and circular linked lists are some of the several varieties of linked lists.
What is the time complexity of inserting an element into a linked list?
The time complexity of inserting an element into a linked list depends on the location of the insertion. If the insertion is at the beginning of the list, the time complexity is O(1). If the insertion is at the end of the list, the time complexity is O(n), where n is the number of elements in the list. If the insertion is at a specific position in the list, the time complexity is also O(n).