Heap heap sort TOPK

A lot ： The parent node is larger than the left and right child
Little heap ： The parent node is smaller than the left and right child nodes

---

Adjust downward

Adjust the algorithm down

Pay attention to the end

1. Is the left and right subtrees over the array end
2. At the right place break get out

problem ：end Is it the number of array elements or the subscript of the last element ？
The subscript of the last element

Error code 1、

void AdjustDown(int* a, int n)
{
    
    assert(a);
    int parent=0;
    int left=2*parent+1;
   	int right=left+1;
    while(left<end)
    {
    
        left=2*parent+1;
   		right=left+1;
		if(a[left]>a[right])
        {
    
             Swap(&a[parent],&a[left]);
             parent=left;
        }
        else
        {
    
             Swap(&a[parent],&a[right]);
             parent=right;
        }
    }
    
}

Correction code 2

void AdjustDown(int* a, int n)
{
    
    assert(a);
    int parent=0,left=0,right=0;
    while(left<end)
    {
    
        left=2*parent+1;
   		right=left+1;
		if(a[left]>a[right])
        {
    
             if(a[parent]<a[left])
             {
    
                 Swap(&a[parent],&a[left]);
            	 parent=left;
             }
             else
             {
    
             	break;   
             }
             
        }
        else
        {
    
             if(a[parent]<a[right])
             {
    
                 Swap(&a[parent],&a[right]);
            	 parent=right;
             }
             else
             {
    
             	break;   
             }
        }
    }
    
}

The final code 3

// Build a pile 
void AdjustDown(int* a, int n, int parent)
{
    
    int child=parent*2+1;
    while(child<end)
    {
    
		if(child+1<n&&a[child+1]>a[child+1])
        {
    
			child=child+1;
        }
        if(a[child]>a[parent])
        {
    
            Swap[&a[parent],&a[child]);
            parent=child;
            child=2*parent+1;
        }
        else
        {
    
            break;
        }
                
    }
    
}

Adjust it up

Adjust the algorithm up

1. The end condition ：child<=0;
2. stay end Insert an element at , Compare with the parent node up , Children change when they are older , Children are no bigger than their father break

Code A lot

void AdJustUp(int* a, int child)
{
    
    int parent=(child-1)/2;
    while(child>0)
    {
    
        if(a[child]>a[parent])
        {
    
            Swap[&a[child],&a[parent]);
            child=parent;
            parent=(child-1)/2;  
        }
        else
        {
    
         	break;            
        }
                    
                      
    }
}

Building the heap - Time complexity analysis

1、 Build a pile down

Code ： Adjust the algorithm down

 // Downward adjustments 
    for(int i=(n-1-1)/2;i>=0;i--)
    {
    
        AdJustDown(a, n, i);
    }

Time complexity analysis （ Downward adjustments ）

2、 Build a pile up

Code ： Adjust the algorithm up

 //  Adjust up 
  for(int i=0;i<sizeof(a)/sizeof(int);i++)
  {
    
       AdJustUp(a,i);
  }

Reactor building complexity analysis （ Adjust up ）

---

atong Knowledge sharing -TopK problem

1、 How to be in n Before the number is selected K Big / Small number

2、 Heap implementation

N Number , Before election K Large number ( Build a small pile - Small pile top )

analysis

Build a small pile ,a[i] Larger than the top of the pile , Swap downward adjustment , The large ones will be adjusted down to the bottom of the pile , Decimals go up , When i Traversing N when , The top of the pile is the second K Big elements

3、 Time complexity analysis

1. build k Number of heaps time complexity

Adjust the build down K Number ：O(K)

2. The following data are compared and adjusted

The worst ,N The number is from small to large , from K+1 The number begins , Each number is larger than the top of the heap element ,K The elements are logK layer , Each number is adjusted logK Time , The time complexity is adjusted to the bottom of the heap ：O((N-K)*logK)

* Overall time complexity ：O(K+(N-K)logK)

4、 Code implementation

void TestTopK(int* a, int n, int k)
{
    
    // Building the heap K Number  a[k-1]  Its father is (k-1-1)/2  Adjust the build down 
    for(int i=(k-1-1)/2;i>=0;i--)
    {
    
        AdJustDown(a, k, i);
    }
    /*  If you don't destroy the original array  int* MinHeap = (int*)malloc(sizeof(int)*k); assert(MinHeap); for (int i = 0; i < k; ++i) { MinHeap[i] = a[i]; } for (int i = (k - 1 - 1) / 2; i >= 0; --i) { AdjustDwon(kMinHeap, k, i); } */
    for(int i=k+1; i<n, i++)
    {
    
        if(a[i]>a[0])
        {
    
            Swap(&a[0], &a[i]);
            AdJustDown(a, k, 0);
        }
    }
}