preface

I’ve obviously been Posting less frequently lately, and that’s because I’m catching up on data structures and algorithms from scratch.

I found a lot of videos and materials, and finally found that the video course of B station is still relatively good, a total of 195 sets. Each section is explained in accordance with the concept, principle, and then code implementation steps. If you’re also ready to get started with data structures and algorithms, I recommend checking out this series of tutorials.

More than 40 episodes were shot in one day yesterday, from the back half of the tree to the whole part of the picture. As you can see, each episode is actually not long, as short as a few minutes, as long as half an hour. Look at it at double speed. It’s so cool.

Without further ado, let’s get to the point.

Introduction to binary heap

As we know, there are many kinds of trees, the most commonly used is the binary tree. Binomial trees have full binomial trees and complete binomial trees. Binary heap is a data structure based on complete binary tree. It has the following two features.

  1. First of all, it’s a complete binary tree
  2. Second, the value of any parent node in the heap is greater than or equal to (or less than) its left and right child nodes.

Therefore, according to the second property, the binary heap is divided into the big top heap (or maximum heap) and the small top heap (or minimum heap).

As the name suggests, a big top heap is a heap whose parents are greater than or equal to the left and right children, and a small top heap is a heap whose parents are smaller than the left and right children.

Take a look at an example diagram of the big top heap. The small top heap is similar, but with smaller values on top.

Note: The big top heap only guarantees that the parent node is larger than the left and right child nodes, and does not guarantee the size order between the left and right child nodes. In the figure, 7’s left child node 6 is larger than right child node 1, while 8’s left child node 4 is smaller than right child node 5. (Same with small top heap)

Build a binary heap

We know the definition of a binary heap, so if I give you a completely unordered binary tree, how do I build it into a binary heap?

Let’s take the big top heap as an example. Given the following array, (complete binary trees are usually stored in arrays)

{4, 1, 9, 3, 7, 8, 5, 6, 2}Copy the code

Let’s draw its initial state, and then analyze how to build the big top heap step by step.

Because of the large top heap, the parent node is larger than the left and right child nodes, so the root node of the tree must have the largest value of all nodes. Therefore, we need to start at the last level of the tree and gradually adjust the values up (swapping the larger nodes of the left and right child nodes with the parent nodes) until we reach the first level.

In fact, to be more specific, the adjustment should start from the non-leaf nodes below. Think about why.

Think about it the other way around. If you start at the first level, such as when you swap 4 and 9, you can’t guarantee that 9 is the maximum for all nodes. If there are more numbers down there than 9, you’ll eventually have to iterate from the bottom up. Well, I might as well have started from the bottom up.

Also, why start from the bottom non-leaf node (node 3 in the figure). Since there are no children under the leaf node, it can only be compared to the parent node, and it makes no sense to start from the leaf node.

The first step is to start with 3 as the parent, compare their children 6 and 2, with 6 being the largest, and then switch places with 3.

Step two, 6 compares with 7, 7 is the largest, 7 and 1 switch places.

Step 3: Compare 7 to 9, 9 is the largest, and 9 and 4 switch places.

In step 4, we find that after switching positions, there are larger nodes below 4, so we also need to compare the parent node of 4 with its left and right children. Eight is found to be the largest, and then eight and four switch places.

Finally, a big top heap is built. The exchange process is implemented in code below.

/** * adjust to big top heap * @param arr array to adjust * @param parent Subscript of the current parent * @param Length how many elements to adjust */ private static void AdjustHeap (int[] arr, int parent, int length){int temp = arr[parent]; Int child = 2 * parent + 1; While (child < length){// Determine the size of the left child node and the right child node, if the right is large, If (child + 1 < length && arr[child] < arr[child + 1]){child ++; If (arr[child] > temp){arr[parent] = arr[child]; if(arr[child] = arr[child]; Parent = child; parent = child; parent = child; parent = child; parent = child; child = 2 * parent + 1; }else{// If the current child node is less than or equal to the parent node, then the parent node is already the maximum, so there is no need to continue the loop break; }} arr[parent] = temp; } public static void main(String[] args) {int[] arr = {4,1,9,3,7,8,5,6,2}; For (int I = arr. Length / 2-1; i >= 0; i--) { adjustHeap(arr,i,arr.length); } System.out.println(Arrays.toString(arr)); } // Print the result: [9, 7, 8, 6, 1, 4, 5, 3, 2]. That's exactly what we found in our analysisCopy the code

In the while loop, the logic for if(arr[Child] > temp) else corresponds to steps 3 and 4 in the figure. You need to make sure that the swapped child node is larger than the child node below it, or you need to continue the loop and adjust the position.

Heap sort

Heap sort is to use the characteristics of the big top heap or small top heap to sort.

The basic idea is:

  1. The current number is woven into a large top heap.
  2. At this point, the root node must be the largest of all nodes, and if you swap it with the last element, the last element will be the maximum.
  3. Reconstructing the remaining n-1 elements into a large top heap yields the maximum number of n-1 elements. Repeating this action will bring all elements into order.

Steps:

Using the array above as an example, let’s look at the heapsort process.

There are nine elements, adjust it to the big top heap, and then swap the top element 9 with the bottom element 2.

At this point, 9 is already in order and does not need to be adjusted. Then adjust the remaining eight elements to the big top heap, and swap the top and bottom elements of these eight elements, as follows: 8 and 3 swap.

At this point, 8 and 9 are already in order and don’t need to be adjusted. Then adjust the remaining seven elements to the big top heap, and swap the top and bottom elements of these seven elements. As follows, 7 and 2 switch places.

And so on, after n-1 cycles of adjustment, when there is only one element left, there is no need to compare, because it is already the minimum.

It may seem like a complicated process, but it’s actually very efficient. You don’t have to add or delete, you can just modify the original array. Because we know that adding and deleting an array is slow, every time we delete, every time we insert, we move n elements behind the array. Plus, it doesn’t take up any extra space.

Code implementation:

Private static void heapSort(int[] arr){private static void heapSort(int[] arr){for (int I = arr.length/2-1; i >= 0; i--) { adjustHeap(arr,i,arr.length); } System.out.println(Arrays.toString(arr)); For (int I = arr. Length - 1; int I = arr. i > 0; Int temp = arr[I]; int temp = arr[I]; int temp = arr[I]; arr[i] = arr[0]; arr[0] = temp; // I represents the number of elements that need to be adjusted in the current array, which is the progressively decreasing adjustHeap(arr,0, I); }}Copy the code

Time complexity and space complexity:

Heap sort takes O(nlogn) for each adjustment to the big top heap, and n elements need to be cycled n-1 times, so the heap sort takes O(nlogn). Its mathematical derivation is more complex, interested students can check the relevant materials.

Since no additional memory space is occupied, the space complexity of heap sort is O(1).