The time complexity of sorting is O (NLGN)

Data structure

(two forks) piles are a array A. This array has two attributes

a.Length: The number of array elements is given 
 A.HEAP-SIZE: How many heap elements are stored in the array 

 The structure of the

pile can be seen as a complete binary tree, the element of dataThe elements in the array are nodes from left to right as trees, a way similar to the hierarchy of the tree.
The height of the node in a pile is the number of nodes to root nodes (there is a difference with the textbook here) on the longest simple path
The height of the height of the pile of n elements is θ (LGN)

• PARENT(i) return Math.floor(i/2): Seeking the bidding of the parent node of the element with the bidding I
• LEFT(i) return 2i: Seek the bidding of the node of the left sub -tree with the bidding I element
• RIGHT(i) return 2i+1: Find the bidding of the node of the right sub -tree with the bidding I element

two forms of binary pile

• maximum pile

  A[PARENT(i)]>=A[i]
  

• minimum pile

  A [Parent (i)] <= a [i], usually used to construct the priority queue

Some basic processes

• MAX-HEAPIFY
• BUILD-MAX-HEAP
• HEAPSORT
• MAX-HEAP-INSERT、HEAP=EXTRACT-MAX、HEAP-INCREASE-KEY、HEAP-MAXIMUM, the function is to use the pile to achieve a limited queue

MAX-HEAPIFY(A,i)

For a node of a tree height N, the time complexity of Max-Heapify is O (H) 

 Maintenance of the nature of the heap 
 Max-heapify (a, i) 
     l = left (i); 
     R = Right (i); 
     if l <= a.head-size and a [i] <a [l] 
         Larget = l; 
     else largest = i; 
     if r <= a.heap-size and a [larget] <A [r] 
         Larget = r; 
     If i is not equal to largest 
         Exchange a [largeset] and a [i] 
         Max-heapify (a, largest)

BUILD-MAX-HEAP

The total time complexity of the total time is O (NLGN), but this upper bound is not gradual and tight, o (n) 

 Use the process from the bottom to use the process of Max-Heapify (a, i) to convert a array of a size n = a.length to the maximum heap to the maximum pile 
 Build-max-heap (a) 
     A.Heap-siZe = a.Length 
     for i = a.Length / 2 double 1 
         Max-heapify (a, i)

HEAPSORT

Time complexity is O (NLGN) 
 Taking the maximum pile as an example, the first element is exchanged with the last element each time, and the size of the pile is reduced by one 
 Heapsort (a) 
     Build-max-heap (a) 
     for i = a.Length downo 2 
         Exchange a [1] with a [i] 
         A.head-size = a.head-size-1 
         Max-heapify (a, 1)

Priority queue

In a heap containing N elements, the operation of all priority queues can be completed within O (LGN) time

• Maximum priority queue

  Application to the operation scheduling of the shared computer system 
   operate: 
       Insert (s, x)) 
       Get maximum value (maximum (s)) 
       Delete and return the maximum value (EXTRACT-MAX (s)) 
       Increase-key (s, x, k)

  MAXIMUM(S)

  maximum (s) 
       Return a [1] # Return to the first value, that is, the maximum pile of the maximum

  HEAP-EXTRACT-MAX(S)

  Heap-Extract-Max (s) 
       if a.heap-size <1 
           error "Heap Underflow" 
       max = a [1] 
       A [1] = a [a.heap-siZe] # Assign the last element to A [1], which is equivalent to deleting the maximum value 
       A.HEAP-SIZE = A.HEAP-SIZE-

  HEAP-INCREASE-KEY(S,x,key)

  Here requires that key must be greater than the current value a [i] 
  
   Heap-discrease-key (s, x, k) 
       if key <A [i] 
           Error "New Key is Smaller Than Curent Key" 
       A [i] = key 
       While I> 1 and A [Parent (i)] <A [i] # Maintain the largest pile of nature 
           Exchange a [Parent (i)] with a [i] 
           i = Parent (i)

  INSERT(S,x)

  HEAP-INSERT(S,key)
      A.heap-size = A.heap-size - 1
      A[A.heap-size] = -∞
      HEAP-INCREASE-KEY(A,A.heap-size,key)
  

• minimum priority queue

  Event -based simulator

Proof of Title

• In a team with height H, what is the minimum number and minimal number of elements?

• Prove: The height of the height of the pile containing n elements is ⌊LGN⌋

Thinking

• Use the insertion method to build a pile

  BUILD-MAX-HEAP'(A)
      A.heap-size = 1
      for i = 2 to A.length
          MAX-INSERT(A,A[i])
  

  When the input is the same, is the built-max-heap and Build-Max-Heap ‘generated the same?

  Not always the same,