Bo2SS

Course Content#

Review [Complete Binary Tree]#

• 

• A complete binary tree is numbered starting from 1

  • This ensures a concise numbering for left and right children
  • [Otherwise] the left child's number would need to be 2 * i + 1, and the right child's number would need to be 2 * i + 2

• The property of numbering → can be stored using sequential structure, without needing to save the address of the next node

  • 
  • Conversion from binary tree → array
  • Stored in the order of level-order traversal, with nodes at each level stored contiguously
  • Here it is stored from index 0, which is 🆗, but not 🆒

Heap [Priority Queue]#

The essential idea is the priority queue, but a heap is just one implementation of a priority queue; a heap is maintained based on a complete binary tree.

Structure Definition#

• The structure is the same as a complete binary tree, but maintains an additional property 👇
  • Max-Heap: For any triplet, the root node value is the largest
  • Min-Heap: For any triplet, the root node value is the smallest

Structure Operations#

All operations must maintain their properties!

• Insertion at the tail [ + adjustment ]
  • Insert the element at the tail, then adjust from bottom to top, adjusting up to the root node
    • Continuously adjust within the triplet, comparing with the parent node, and do not stop until a swap occurs, until reaching the root node
    • Swapping only changes the relative size of the swapped elements; the overall relative size relationship of the structure remains unchanged
  • The indices compared are actually i and i / 2
  • Time complexity: O(log[2]N), which is the height of the tree
• Popping from the head [ + adjustment ]
  • Move the last element to the top of the heap, then adjust from top to bottom, until the element has no children
    • Continuously adjust within the triplet, comparing with child nodes, and do not stop until there are no children
    • Why choose the last element to move to the top of the heap?
    • Because if you take an element from another position, who will fill the gap left by this element?
  • The indices compared are actually i, 2 * i, and 2 * i + 1
  • Time complexity: also the height of the tree
• [PS]
  • Max-Heap: Convenient for finding the 1st and 2nd largest elements [root node, second layer]
    • Finding the 3rd largest, 4th largest... is not so simple, as it is inconvenient to determine the layer
  • ❗ The above process
    • Elements enter the queue from the tail, and elements exit the queue from the head 👉 same queue
    • The element exiting the queue is the extreme value 👉 also known as a priority queue

Heap Sort#

• Based on its properties, popping all elements will yield a sorted sequence
• ⭐ Change in thinking: The pop operation of the top element of the heap ==> Swap the top element with the tail element of the heap
  • 【This operation】
  • All elements of the Max-Heap popped 👉 the original array stores a sorted sequence from smallest to largest
  • [Thus, from a Max-Heap, we obtain a special Min-Heap, because generally popped elements are placed at the end of the original array]
• Time complexity: O(NlogN)
  • The time consumed is in the adjustment operations, with each adjustment having a time complexity of O(logN), and there are N elements, requiring N - 1 adjustments
  • The time complexity of the pop operation is O(1)
  • Time efficiency will not degrade

Building a Heap#

[To use heap sort, you first need to maintain a heap, which means building a heap from a regular sequence build heap, with two approaches below]

Conventional Approach#

Also known as the insertion heap building method

• According to the aforementioned tail insertion adjustment method: from bottom to top
  • Starting from level 0 [default root node at level 0], calculate the maximum number of adjustments for each level:
  • 
  • The number of adjustments at level i is i, and the number of nodes at level i is 2 ^ i → the total number of adjustments at level i is i * (2 ^ i)
• The worst-case time complexity for building a heap is O(NlogN), with the calculation process as follows:
  • Total number of adjustments S = (n - 1) * 2 ^ (n + 1) + 1, process as follows:
    • 
    • Using the method of cancellation of split terms
  • The above n corresponds to [number of layers - 1] [starting from level 0 to level n, the number of layers is n + 1], if we let the total number of nodes be N, then n ≈ log[2]N
  • ❗【Conversion from number of layers n to number of nodes N】 Substitute n ≈ log[2]N into S, yielding S ≈ Nlog[2]N
  • Thus, the worst-case time complexity is: O(NlogN)

Linear Approach ⭐#

Also known as the [Linear Heap Building Method]

• 

• As shown in the figure

  • Conventional approach: The lower the layer, the more adjustments needed, which means greater weight
  • ❗ So can we reverse our thinking and place greater weights at the front, reducing the weight of layers with more child nodes?
  • Linear approach: Yes! Start from the second to last layer, adjusting from [top to bottom]

• 🆒 The worst-case time complexity for building a heap is O(N)

  • Similarly, using the method of cancellation of split terms, the total number of adjustments S = 2 ^ (n + 1) - 2 - n
  • Converting the number of layers n to the number of nodes N gives S ≈ 2N - 2 - log[2]N
  • Thus, the worst-case time complexity is: O(N)

• ⭐ Recommended video Linear Time BuildHeap——Youtube

  • Compares the conventional heap building and linear heap building methods, with intuitive animated demonstrations to deepen understanding

Code Demonstration#

Heap [Priority Queue]#

• 
• 

• Adjustment operation, cleverly using variables ind, temp, l, r

  • ind stops adjusting under certain conditions
  • Pay attention to whether ind [entering heap, exiting heap], r [exiting heap] exists

Linear Heap Building Method#

• 
• 

• Here, [heap sort] considers [building a heap] + [sorting]

  • O(N) + O(NlogN) = O(NlogN)

• No heap structure is defined, using an array to simulate the heap

• Line 33: Heap node numbering starts from 1 for convenience, so here arr-1 is to unify the array index by shifting it left by one int size

• Encapsulated the top-down adjustment method, as can be seen from the following figure, the first adjustment position comes from the previously recommended video Linear Time BuildHeap——Youtube

• 

Points to Consider#

• ❌ The time complexity corresponding to n layers of loops is O(N^n), we must abandon fixed thinking and analyze the essence!
• 

Tips#

Course Summary#