Comments (heap sort resolution)

JS heap sort

The heap is a complete binary tree.
Complete binary tree: except for the last layer of binary tree, the number of nodes of other layers reaches the maximum, and all nodes of the last layer are concentrated on the left side (only when the left side is full can the right side be missing).
Big top heap: the root node is the maximum value, and the value of each node is greater than or equal to the value of its child node.
Small top heap: the root node is the minimum value, and the value of each node is less than or equal to the value of its child node.
Heap storage: heap by array to achieve, equivalent to binary tree to do sequence traversal.

① If you want a descending sequence, form a big top heap for a given array, then put the root node of the big top heap in the last bit of the array, and continue to form a big top heap before the last bit, and finally form a descending sequence
② The ascending sequence can be reversed

The minimum number of k

Input integer array arr, find out the smallest k number. For example, if you enter 8 numbers 4, 5, 1, 6, 2, 7, 3 and 8, the minimum 4 numbers are 1, 2, 3 and 4.

Example 1:
Input: arr = [3,2,1], k = 2
 Output:[1,2] perhaps [2,1]
Example 2:
Input: arr = [0,1,2,1], k = 1
 Output:[0]

Solution 1

Sorting by array built-in function

var getLeastNumbers = function(arr, k) {
    return arr.sort((a,b) => a-b).slice(0,k)
};

In fact, it is quick sort. The time complexity is O(NlogN), and the space complexity is O(logN)

Solutions 2

Using the maximum heap, get the sorted array

function swap(A, i, j) {
  let temp = A[i];
  A[i] = A[j];
  A[j] = temp; 
}
function shiftDown(A, i, length) {
  let temp = A[i]; // Current parent node
// The purpose of J < length is to adjust the order of all nodes below node i
  for(let j = 2*i+1; j<length; j = 2*j+1) {
    temp = A[i];  // Take out A[i], and the whole process is equivalent to finding out where A[i] should be
    if(j+1 < length && A[j] < A[j+1]) { 
      j++;   // Find the older of the two children and compare with the parent node
    }
    if(temp < A[j]) {
      swap(A, i, j) // If the parent node is smaller than the child node: swap; Or jump out
      i = j;  // After swapping, the subscript of temp becomes j
    } else {
      break;
    }
  }
}
function heapSort(A) {
  // Initialize the top heap, starting from the first non leaf node
  for(let i = Math.floor(A.length/2-1); i>=0; i--) {
    shiftDown(A, i, A.length);
  }
  // Sort, each time for loop to find a current maximum, array length minus one
  for(let i = Math.floor(A.length-1); i>0; i--) {
    swap(A, 0, i); // The root node exchanges with the last node
    shiftDown(A, 0, i); // The adjustment starts from the root node, and the last node is the current node
                         // Before the maximum value, do not need to participate in the comparison, so the third parameter
                         // It is i, that is to say, it can be compared to the one before the last node
  }
}
var getLeastNumbers = function(arr, k) {
    heapSort(arr)
    return arr.slice(0,k)
};

The complexity of shift down is O(logn), while the outer loop has f(n) times, so the final complexity is O(nlogn)

Median in data stream

How to get a median in a data stream? If an odd number of values are read from the data stream, the median is the value in the middle after all values are sorted. If an even number of values are read from the data stream, the median is the average of the middle two numbers after all the values are sorted.
For example,
The median of [2,3,4] is 3
The median of [2,3] is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
void addNum(int num) - adds an integer from the data stream to the data structure.
Double findmedium () - returns the median of all elements at present.

Example 1:
Input:
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
Output:[null,null,null,1.50000,null,2.00000]
Example 2:
Input:
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
Output:[null,null,2.00000,null,2.50000]

Solution 1

Violence law
Each time the median is taken out, all elements are sorted first, and then the median is calculated.

var MedianFinder = function() {
    this.data = [];
};
MedianFinder.prototype.addNum = function(num) {
    this.data.push(num);
};
MedianFinder.prototype.findMedian = function() {
    const length = this.data.length;
    if (!length) {
        return null;
    }
    this.data.sort((a, b) => a - b);
    const mid = Math.floor((length - 1) / 2);
    if (length % 2) {
        return this.data[mid];
    }
    return (this.data[mid] + this.data[mid + 1]) / 2;
};

Solutions 2

Binary search
In fact, you don't need to reorder all the elements every time you add them. If you always ensure that the elements are in order, when you add new elements, you only need to insert the elements into the correct position. You can find the correct position by "binary search".
In order to keep the previous elements in order, put them in the correct position for each newly added element.

var MedianFinder = function() {
    this.data = [];
};

MedianFinder.prototype.addNum = function(num) {
    if (!this.data.length) {
        this.data.push(num);
        return;
    }

    let left = 0,
        right = this.data.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (this.data[mid] === num) {
            this.data.splice(mid, 0, num);
            return;
        } else if (this.data[mid] < num) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    this.data.splice(right + 1, 0, num);
};

MedianFinder.prototype.findMedian = function() {
    const length = this.data.length;
    if (!length) {
        return null;
    }

    const mid = Math.floor((length - 1) / 2);
    if (length % 2) {
        return this.data[mid];
    }
    return (this.data[mid] + this.data[mid + 1]) / 2;
};

Binary search needs O(logN) complexity, and moving elements needs O(N) complexity, so the time complexity is O(N).

Solution 3

Size heap (bridge mode)
Using the idea of maximum heap or minimum heap, the time complexity of the library is too high and the AC can not be used.
Heap is an excellent solution for this kind of dynamic data. Prepare two heaps:
Maximum heap: holds the smaller half of the data stream
Minimal heap: stores the larger half of the data stream
It is necessary to ensure the "balance" of these two heaps. The balance here is: Max heap size = min heap size, or max heap size = min heap size + 1.
When findmedium is called to query the median, the median is the top element of the largest heap, or (top element of the largest heap + top element of the smallest heap) / 2
The rest of the problem is how to balance the heap? The steps are as follows
Let num enter maxHeap first
Take out the top element of maxHeap and put it into minHeap
If the maximum heap size is less than the minimum heap size, take out the top element of minHeap and let it enter maxHeap

const defaultCmp = (x, y) => x > y; // The default is maximum heap
const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
class Heap {
    /**
     * The default is maximum heap
     * @param {Function} cmp
     */
    constructor(cmp = defaultCmp) {
        this.container = [];
        this.cmp = cmp;
    }

    insert(data) {
    	//It's equivalent to binding this for the following container and cmp, so you don't need to write this.container and so on
        const { container, cmp } = this;

        container.push(data);
        let index = container.length - 1;
        while (index) {
            let parent = Math.floor((index - 1) / 2);
            if (!cmp(container[index], container[parent])) {
                return;
            }
            swap(container, index, parent);
            index = parent;
        }
    }

    extract() {
        const { container, cmp } = this;
        if (!container.length) {
            return null;
        }

        swap(container, 0, container.length - 1);
        const res = container.pop();
        const length = container.length;
        let index = 0,
            exchange = index * 2 + 1;

        while (exchange < length) {
            // //In the case of maximum heap: if there is a right node, and the value of the right node is greater than that of the left node
            let right = index * 2 + 2;
            if (right < length && cmp(container[right], container[exchange])) {
                exchange = right;
            }
            if (!cmp(container[exchange], container[index])) {
                break;
            }
            swap(container, exchange, index);
            index = exchange;
            exchange = index * 2 + 1;
        }

        return res;
    }

    top() {
        if (this.container.length) return this.container[0];
        return null;
    }
}


var MedianFinder = function() {
    this.maxHeap = new Heap();
    this.minHeap = new Heap((x, y) => x < y);
};

MedianFinder.prototype.addNum = function(num) {
    this.maxHeap.insert(num);
    this.minHeap.insert(this.maxHeap.top());
    this.maxHeap.extract();

    if (this.maxHeap.container.length < this.minHeap.container.length) {
        this.maxHeap.insert(this.minHeap.top());
        this.minHeap.extract();
    }
};

MedianFinder.prototype.findMedian = function() {
    return this.maxHeap.container.length > this.minHeap.container.length
        ? this.maxHeap.top()
        : (this.maxHeap.top() + this.minHeap.top()) / 2;
};