Today share a relatively simple topic, I hope you can master in 5 minutes!

01. Examples of topics

The smallest number of k
Enter the integer array arr to find the smallest k number. For example, if you enter 4, 5, 1, 6, 2, 7, 3, and 8, the smallest four digits are 1, 2, 3, and 4.

Example 1:

Input: arr = [3,2,1], k = 2Output: [1,2] or [2,1]Copy the code

Example 2:

Input: arr = [0,1,2,1], k = 1Output: [0]Copy the code

Limitations:

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
Copy the code

02, Heap and size top heap

This question comes from “Finger offer”, which is a very frequent question. It can be solved by sorting and so on. But here, we use the more classical ** big top heap (big root heap) ** solution to solve. Because I know a lot of people are probably confused, so let’s go over the big top heap.

A Heap is a general term for a special kind of data structure in computer science. We usually refer to an array object that can be viewed as a complete binary tree. If you don’t remember what a complete binary tree is, you can review this article:

Binomial Trees Lecture 7 – Complete Binomial Trees (222)

The property of the heap is that the value of the parent node is always greater or smaller than the value of its two children. If the parent node is larger than both of its children, we call it the big top heap. If the parent node is smaller than both of its children, we call it the small top heap.


We number the nodes in the heap by layer, and we map this logical structure to an array like this.


The big top heap satisfies the following formula:

arr[i] >= arr[2i 1] && arr[i] >= arr[2i 2]

The same goes for the small top heap:


The small top heap satisfies the following formula:

arr[i] <= arr[2i 1] && arr[i] <= arr[2i 2]

03. Topic analysis

We learned about the big top heap, now let’s think about how to solve it with the big root heap.

First, we create a large top heap of size K. If the array is [4,5,1,6,2,7,3,8], k=4. Something like this:


I’m sure there are some people here who don’t know how to build stacks. Remember: For an unmaintained heap (a complete binary tree), we can start tweaking from the parent of its last node. This does not need to memorize, in fact, is a layer of adjustment process.


Adjusts from the parent of the last node


Keep going up


Keep going up


The code for heap adjustment looks something like this:

/ / build the heap. For a heap that has not yet been maintained, adjust from the parent of its last node.
private void buildHeap(int[] nums) { 
    // The last node
    int lastNode = nums.length - 1; 
    // Remember: parent = (i-1) / 2 left = 2 * I 1 right = 2 * I 2;
 // The parent of the last node is 7  int startHeapify = (lastNode - 1) / 2;  while (startHeapify >= 0) {  // Adjust the heap building process  heapify(nums, startHeapify--);  } }  // The process of adjusting the big top heap private void heapify(int[] nums, int i) {  // If there is a larger number of nodes than the left and right nodes of the current node, then switch and continue the maintenance of the switched node  int len = nums.length;  if (i >= len)  return;  // Left and right child nodes  int c1 = ((i << 1) 1), c2 = ((i << 1) 2);  // Assume that the current node is the largest  int max = i;  // If the left child node is large, update Max = c1;  if (c1 < len && nums[c1] > nums[max]) max = c1;  // If the right child node is large, update Max = c2;  if (c2 < len && nums[c2] > nums[max]) max = c2;  // If the largest number is not node I, heapify(nums, Max) adjusts the subtree of node I.  if(max ! = i) { swap(nums, max, i);  // recursive processing  heapify(nums, max);  } } private void swap(int[] nums, int i, int j) {  nums[i] = nums[i] nums[j] - (nums[j] = nums[i]); } Copy the code

Then we iterate through the rest of the array starting with k. If the element is smaller than the heaptop element, the heaptop element is fetched and the current element is added to the heap. In the example above, 2 is put into the heap because it is less than the top of the heap element 6. We found that the current complete binary tree does not satisfy the big top heap, so we adjusted it.


Before the adjustment


After the adjustment


Repeat the above steps, adding 7,3, and 8 to the heap. Here, since 7 and 8 are bigger than 5 at the top of the heap, only 3 will go in.


Before the adjustment


After the adjustment


The heap that we end up with is what we want. Since the size of the heap is K, the space complexity is O(K) and the time complexity is O(NlogK).


According to the analysis, complete the code:

//java
class Solution { 
    public int[] getLeastNumbers(int[] arr, int k) { 
        if (k == 0) 
            return new int[0]; 
 int len = arr.length;  if (k == len)  return arr;  // Create a heap for the first k of the arR array  int[] heap = new int[k];  System.arraycopy(arr, 0, heap, 0, k);  buildHeap(heap);   // Build a heap for the smaller trees behind  for (int i = k; i < len; i++) {  if (arr[i] < heap[0]) {  heap[0] = arr[i];  heapify(heap, 0);  }  }  // Return the heap  return heap;  }  private void buildHeap(int[] nums) {  int lastNode = nums.length - 1;  int startHeapify = (lastNode - 1) / 2;  while (startHeapify >= 0) {  heapify(nums, startHeapify--);  }  }  private void heapify(int[] nums, int i) {  int len = nums.length;  if (i >= len)  return;  int c1 = ((i << 1) 1), c2 = ((i << 1) 2);  int max = i;  if (c1 < len && nums[c1] > nums[max]) max = c1;  if (c2 < len && nums[c2] > nums[max]) max = c2;  if(max ! = i) { swap(nums, max, i);  heapify(nums, max);  }  }  private void swap(int[] nums, int i, int j) {  nums[i] = nums[i] nums[j] - (nums[j] = nums[i]);  } } Copy the code

Execution Result:



I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download

And small hao learning algorithm