Heap: Structure and Applications, Introduction to Min-Heap and Max-Heap
A heap is a special type of complete binary tree, characterized by the size relationship between parent and child nodes (parent ≤ child for a min-heap, parent ≥ child for a max-heap). It efficiently retrieves extreme values (with the top element being the minimum or maximum), similar to a priority queue. The underlying structure is a complete binary tree, where each level is filled as much as possible, and the last level is filled from left to right. When stored in an array, the left child index is 2i+1, the right child index is 2i+2, and the parent index is (i-1)//2. Basic operations include insertion (appending to the end and then "bubbling up") and deletion (replacing the top element with the last element and then "bubbling down"), both with a time complexity of O(log n). Heaps are widely used in priority queues (e.g., task scheduling), finding the k-th largest element, and Huffman coding. They are a critical structure for efficiently handling extreme value problems.
Read MoreWhat is a Heap? A Detailed Explanation of Basic Operations on Heaps in Data Structures
A heap is a special structure based on a complete binary tree, stored in an array, and satisfies the properties of a max heap (parent node value ≥ child node) or a min heap (parent node value ≤ child node). It can efficiently retrieve the maximum or minimum value and is widely used in algorithms. The array indices map parent-child relationships: left child is at 2i+1, right child at 2i+2, and parent is at (i-1)//2. A max heap has the largest root (e.g., [9,5,7,3,6,2,4]), while a min heap has the smallest root (e.g., [3,6,5,9,7,2,4]). Core operations include insertion (appending new element to the end and adjusting upward to satisfy heap property), deletion (swapping root with last element and adjusting downward), heap construction (adjusting from the last non-leaf node downward), and retrieving the root (directly accessing the root node). It is applied in priority queues, heap sort, and Top K problems. The efficient structure and operations of heaps are crucial for understanding algorithms, and beginners can start with array simulation to master them.
Read More