Heap operation

Need to know ：

Heap must be a complete binary tree
If the parent node is the subscript of the array i, Then the left and right child nodes are ：2*i+1、2*i+2
If the child node is j, Then its parent node is (j-1)/2

Build the heap structure 、 Delete the heap element to 【 sinking 】 operation

Insert elements to 【 Go up 】 operation

How to build this array into a small top heap structure ？

int arr[] = {15,12,17,30,50,20,60,65,4,19};

Original structure ：

First step ： Take the last non leaf node in the original heap structure 【i】, take 【i】 and 【2*i+1】 and 【2*i+2】 Compare the elements of , If there is a ratio 【i】 Small elements , swapping , And set the subscript of the smaller child node as the subscript of the current node to be compared , Until for 【i】 Meet the small top pile or stop at the leaf node , This operation is 【 sinking 】 operation

The construction process is shown in the figure ：

The core is to find the correct position of each non leaf node in the small top pile  

The code is as follows ：

template <class T>
void Heap<T>::FilterDown(int i)
{
	int  currentPos = i;
	int childPos = 2 * i + 1;
	T target = hList[currentPos];
	// If the intermediate process does not meet the heap condition , Compare it all the way to the leaf node of the last layer 
	while (childPos < heapSize)
	{
		// Compare the current node with the child's smaller node elements 
		if (childPos + 1 < heapSize && hList[childPos + 1] < hList[childPos])
			childPos = childPos + 1;
		// The current node is smaller than its child node , To meet the small top pile , Find the right position 
		if (target <= hList[childPos])
			break;
		else
		{
			hList[currentPos] = hList[childPos];
			currentPos = childPos;
			childPos = currentPos * 2 + 1;
		}
	}
	hList[currentPos] = target;
}

  For each element in the original array in turn （ From the last non leaf node to the top of the heap 【0】 The order of ） Conduct 【 Sinking operation 】, Finally, it is built into a small top pile structure （ The same is true for the big top pile , Just exchange elements with older children ）

	// The index of the last heap element is  n-1, Then its parent index is (n-1-1)/2 = (n-2)/2
	currentPos = (heapSize - 2) / 2;    //heapSize For the size of the array 
	// Sink each non leaf node in turn 
	while (currentPos >= 0)
	{
		FilterDown(currentPos);
		currentPos--;
	}

Insert elements ： Put the inserted element at the end of the extended array , Conduct 【 Go up 】 Find the right place

Insert elements into the small top heap 8, Because the structure is already a small top pile , So just go up and find the right place

template <class T>
void Heap<T>::Insert(const T& item)
{
	if (heapSize == maxHeapSize)
	{
		cout << "Heap full";
		return;
	}
		// Store elements at the end of the heap , And make the heap size +1, And call FilterUp() Float the element up to find the right position 
		hList[heapSize] = item;
		heapSize++;
		FilterUp(heapSize);
}

template <class T>
void Heap<T>::FilterUp(int i)
{
	//curretnPos  To traverse the subscript on the parent path ,target by hList[i] Value , And be relocated in the path 
	int currentPos = i;
	int parentPos = (i - 1) / 2;
	T target = hList[i];
	// Follow the parental path to the root 
	while (currentPos != 0)
	{
		// The current subscript position has met the small top pile condition , There is no need to compare up 
		if (hList[parentPos] <= target)
			break;
		else
		{
			// The value of the current node is smaller than that of the parent node , Continue to look up for a position 
			hList[currentPos] = hList[parentPos];		// The parent node element moves down 
			currentPos = parentPos;
			parentPos = (currentPos - 1) / 2;
		}
	}
	// Found the correct location of the current node 
	hList[currentPos] = target;
}

Remove elements ：

First, the element to be deleted （ Whether at the top of the heap or in the heap ） Exchange with the tail element of the array , And reduce the operable size of the heap -1, Then heap the deleted subscript elements 【 sinking 】, Find its correct position in the heap

for example ： Remove the heap top element 4 The following structure is shown in the figure

// Return to the first element in the heap and modify the heap 
template<class T>
T Heap<T>::Delete()
{
	T tempItem;
	if (heapSize == 0)
	{
		cout << "Heap empty";
		return -1;
	}
		
	// Remove the heap top element , And put the last element at the top of the heap , And sink the element to the correct position to meet the small top pile 
	tempItem = hList[0];
	hList[0] = hList[heapSize - 1];
	heapSize--;
	FilterDown(0);			// The top element sinks to the right position 
	return tempItem;		// Return to the top of heap element 
}

Heap sort ： Is to constantly delete the top elements

// The algorithm complexity of heap sorting is ：O(nlog2n)
template <class T>
void Heap<T>::HeapSort(T a[],int n)
{
	T element;
	for (int i=0;i<n;i++)
	{
		element = this->Delete();
		a[i] = element;
	}
}