JS Data Structure and Algorithm “heap”

concept

The bottom of the heap is actually a full binary tree, which can be implemented as an array.

A binary tree that satisfies the following conditions:

1. Any node is greater than or less than all of its children (large root heap, small root heap)
2. Always a complete tree, that is, all nodes except the lowest level are filled with elements

The heap with the largest root node is called the maximum heap or large root heap, and the heap with the smallest root node is called the minimum heap or small root heap.

Set the first element of the array to empty to facilitate computation. So we can start with the subscript 1, the subscript variable is I, so:

• The left child node position is2*i
• The position of the right child node is2*i+1
• The location of the parent node isMath.floor(i/2)

The operations related to the heap (for example, the large top heap) are as follows:

1. Max-heapify, where children at the end of the heap are adjusted so that the children are always smaller than the parent;
2. Create a build-max-heap and position all the data in the Heap to make it a big top Heap.
3. Heap-sort, which removes the root node at the top of the Heap and iterates the top Heap adjustment.

Big top stack adjustment

/** * Check from index and keep large top heap * @param arr * @param I check starting subindex * @param size heap size */
function maxHeapify(arr, i, size) {
  let left = 2 * i
  let right = left + 1

  // The older of the children
  let maxlr = - 1

  // There is no left or right child node
  if (left > size && right > size) {
    return
  }
  // Only the left child node
  if (left <= size && right > size) {
    maxlr = left
  }
  // Only the right child node
  if (right <= size && left > size) {
    maxlr = right
  }
  // There are both left and right child nodes
  if (left <= size && right <= size) {
    maxlr = arr[left] < arr[right] ? right : left
  }

  if (arr[i] < arr[maxlr]) {
    swap(arr, i, maxlr)
    maxHeapify(arr, maxlr, size)
  }
}

function swap(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}
Copy the code

Non-recursive writing:

/** * check from I and keep large top heap * @param arr * @param I check start subindex * @param size heap size */
function maxHeapify2(arr, i, size) {
  let left, right, maxlr = - 1

  while (i < size) {
    left = 2 * i
    right = left + 1

    // There is no left or right child node
    if (left > size && right > size) {
      break
    }
    // Only the left child node
    if (left <= size && right > size) {
      maxlr = left
    }
    // Only the right child node
    if (right <= size && left > size) {
      maxlr = right
    }
    // There are both left and right child nodes
    if (left <= size && right <= size) {
      maxlr = arr[left] < arr[right] ? right : left
    }

    if (arr[i] < arr[maxlr]) {
      swap(arr, maxlr, i)
      i = maxlr
    }
  }
}

function swap(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}
Copy the code

Create a large top heap

Build-max-heap is used to transform an array into a large top Heap, using bottom-up calls to max-heapify to transform the array.

function buildMaxHeap(arr) {
  if (!Array.isArray(arr)) return []

  // Insert null into the first position of the array
  arr.unshift(null)
  let lastParentIndex = Math.floor((arr.length - 1) / 2)
  for (let i = lastParentIndex; i > 0; i--) {
    maxHeapify(arr, i, arr.length - 1)
  }
  arr.shift()
}
Copy the code

Heap sort

Heap-sort is an interface algorithm for heapsort. It first calls build-max-heap to transform the array into a big top Heap. We then go to an iteration, where we swap the elements at the top of the heap with the bottom of the heap, shorten the heap length, and then re-call max-heapify to keep the big top.

Since the top element of the heap must be the largest element in the heap, after each operation, the largest element in the heap will be separated out of the heap, repeated n-1 times, and the array sort is complete.

function heapSort(arr) {
  arr[0]! = =null && arr.unshift(null)
  for (let j = arr.length - 1; j > 0; j--) {
    // Swap the elements at the top of the heap with the elements at the bottom of the heap to separate out the largest element
    swap(arr, 1, j) 
    // Readjust the big top heap
    maxHeapify(arr, 1, j - 1)
  }
  arr.shift()
}
Copy the code

Let’s test building and sorting the large top heap:

var arr = [5.2.8.3.1.6.9]
buildMaxHeap(arr)
console.log(arr)
heapSort(arr)
console.log(arr)

/ /,3,8,2,1,6,5 [9]
/ /,2,3,5,6,8,9 [1]
Copy the code

The complexity of the

Heap sort is a selection sort, the whole mainly consists of building the initial heap + swapping the top and the end of the heap elements and rebuilding the heap two parts.

Among them, the complexity of building the initial heap is O(n). In the process of swapping and rebuilding the heap, n-1 exchange is required. In the process of rebuilding the heap, according to the properties of complete binary tree, [log2(n-1),log2(n-2)…1] decreases gradually, approximately to Nlogn.

So the heapsort time is generally thought to be order nlogn.

Add elements

Add the elements to the end of the array, and then make the big top heap adjustment

function maxHeapPush(arr = [], elem) {
  arr.push(elem)
  arr[0]! = =null && arr.unshift(null)
  let lastParentIndex = Math.floor((arr.length - 1) / 2)
  for (let i = lastParentIndex; i > 0; i--) {
    maxHeapify(arr, i, arr.length - 1)
  }
  arr.shift()
}
Copy the code

Pop-up element

If we delete the root element directly, the whole heap will be destroyed. So we think about replacing the root node with an internal element. This element is obviously the last element, because the movement of the last element does not change the structure of the tree. After the exchange, the large top heap adjustment is carried out.

function maxHeapPop(arr = []) {
  arr[0]! = =null && arr.unshift(null)
  swap(arr, 1, arr.length - 1)
  const top = arr.pop()

  let lastParentIndex = Math.floor((arr.length - 1) / 2)
  for (let i = lastParentIndex; i > 0; i--) {
    maxHeapify(arr, i, arr.length - 1)
  }
  arr.shift()
  return top
}
Copy the code

Test it out:

var arr = [5.2.8.3.1.6.9]
buildMaxHeap(arr)
console.log(arr)
maxHeapPush(arr, 10)
console.log(arr)
maxHeapPop(arr)
console.log(arr)

//[10, 9, 8, 3, 1, 6, 5, 2]
//[9, 3, 8, 2, 1, 6, 5]
Copy the code

Encapsulated, the complete code looks like this:

function Heap(type = 'max') {
  this.type = type
  this.arr = []
}

Heap.prototype.build = function() {
  this.arr.unshift(null)
  let lastParentIndex = Math.floor((this.arr.length - 1) / 2)
  for (let i = lastParentIndex; i > 0; i--) {
    this.heapify(i, this.arr.length - 1)}this.arr.shift()
}

Heap.prototype.heapify = function(i, size) {
  let left = 2 * i
  let right = left + 1

  // One of the older or younger children
  let lr = - 1

  // There is no left or right child node
  if (left > size && right > size) {
    return
  }
  // Only the left child node
  if (left <= size && right > size) {
    lr = left
  }
  // Only the right child node
  if (right <= size && left > size) {
    lr = right
  }
  // There are both left and right child nodes
  if (left <= size && right <= size) {
    lr = this.type === 'max' ? (this.arr[left] < this.arr[right] ? right : left) : (this.arr[left] > this.arr[right] ? right : left)
  }

  if ((this.type === 'max' && this.arr[i] < this.arr[lr]) || (this.type === 'min' && this.arr[i] > this.arr[lr])) {
    this.swap(i, lr)
    this.heapify(lr, size)
  }
}

Heap.prototype.sort = function() {
  this.arr[0]! = =null && this.arr.unshift(null)
  for (let j = this.arr.length - 1; j > 0; j--) {
    this.swap(1, j)
    this.heapify(1, j - 1)}this.arr.shift()
}

Heap.prototype.add = function(elem) {
  this.arr.push(elem)
  this.arr[0]! = =null && this.arr.unshift(null)
  let lastParentIndex = Math.floor((this.arr.length - 1) / 2)
  for (let i = lastParentIndex; i > 0; i--) {
    this.heapify(i, this.arr.length - 1)}this.arr.shift()
}

Heap.prototype.pop = function() {
  this.arr[0]! = =null && this.arr.unshift(null)
  this.swap(1.this.arr.length - 1)
  const top = this.arr.pop()

  let lastParentIndex = Math.floor((this.arr.length - 1) / 2)
  for (let i = lastParentIndex; i > 0; i--) {
    this.heapify(i, this.arr.length - 1)}this.arr.shift()
  return top
}

Heap.prototype.swap = function(i, j) {
  let temp = this.arr[i]
  this.arr[i] = this.arr[j]
  this.arr[j] = temp
}

var heap = new Heap()
heap.add(5)
heap.add(2)
heap.add(8)
heap.add(3)
heap.add(1)
heap.add(6)
heap.add(9)
console.log(heap.arr)

//heap.build()
//console.log(heap.arr)

heap.add(10)
console.log(heap.arr)

heap.pop()
console.log(heap.arr)

heap.sort()
console.log(heap.arr)
Copy the code

The median in a data stream

How do I get the median in a data stream? If an odd number of values are read from the data stream, then the median is the number in the middle after all the values are sorted.

If an even number of values are read from the data stream, then the median is the average of the two middle numbers after all the values are sorted. We use the Insert() method to read the data stream and the GetMedian() method to get the median of the data currently read.

Steps:

1. Maintain a large top heap, a small top heap, and the total number of data:

• The values in the small top heap are all greater than those in the large top heap;
• The difference between two heap counts is less than or equal to 1

2. When the total number of data after insertion is odd: the number of small top heap is 1 more than the number of large top heap; When the number of inserted numbers is even, the number of large top heaps is the same as the number of small top heaps.
3. When the total number of numbers is odd, the median is the small top pile; When the total number of numbers is even, the median number is the average of the two heaps.

const maxHeap = new Heap('max');
const minHeap = new Heap('min');
let count = 0;
function Insert(num) {
  count++;
  if (count % 2= = =1) {
    maxHeap.add(num);
    minHeap.add(maxHeap.pop());
  } else{ minHeap.add(num); maxHeap.add(minHeap.pop()); }}function GetMedian() {
  if (count % 2= = =1) {
    return minHeap.value[0];
  } else {
    return (minHeap.value[0] + maxHeap.value[0) /2}}Copy the code

The smallest k number

Enter n integers and find the smallest K of them. For example, if you input 4,5,1,6,2,7,3,8, the smallest four numbers are 1,2,3,4.

Steps:

1. Build the first K numbers into a big top heap
2. Start with the KTH number and compare it to the maximum value of the large top heap. If it is less than the maximum value, switch the positions of the two numbers and rebuild the large top heap
3. The number in the top heap after one walk is the smallest k number in the whole data

function getLeastNumbers(arr, k) {
  if (k > arr.length) {
    return []
  }
  arr.unshift(null)
  buildMaxHeap(arr, k + 1)

  for (let i = k + 1; i < arr.length; i++) {
    if (arr[i] < arr[1]) {
      [arr[i], arr[1]] = [arr[1], arr[i]]

      let lastParentIndex = Math.floor(k / 2)
      for (let j = lastParentIndex; j > 0; j--) {
        maxHeapify(arr, j, k)
      }
    }
  }
  return arr.slice(1, k + 1)}function buildMaxHeap(arr, size) {
  let lastParentIndex = Math.floor(size / 2)
  for (let i = lastParentIndex; i > 0; i--) {
    maxHeapify(arr, i, size)
  }
}

function maxHeapify(arr, i, size) {
  let left = 2 * i
  let right = left + 1

  // The older of the children
  let maxlr = - 1

  // There is no left or right child node
  if (left > size && right > size) {
    return
  }
  // Only the left child node
  if (left <= size && right > size) {
    maxlr = left
  }
  // Only the right child node
  if (right <= size && left > size) {
    maxlr = right
  }
  // There are both left and right child nodes
  if (left <= size && right <= size) {
    maxlr = arr[left] < arr[right] ? right : left
  }

  if (arr[i] < arr[maxlr]) {
    [arr[i], arr[maxlr]] = [arr[maxlr], arr[i]]
    maxHeapify(arr, maxlr, size)
  }
}


var arr = [4.5.1.6.2.7.3.8]
var result = getLeastNumbers(arr, 4)
console.log(result)
/ /,3,1,2 [4]
Copy the code