Large top heap, small top heap and heap sequencing

Heap structure is a special logical structure , Through the heap sorting algorithm, the disorder can be stacked O(logn) The time sequence is a large top heap or a small top heap , So as to quickly obtain the maximum and minimum values .

1. The physical and logical structure of the heap

The logical structure of the heap is a Perfect binary tree , The actual physical structure in memory is a Sequential array .

A complete binary tree is a kind of tree in which every layer is Value from left to right until the layer is full, and then it will grow to a deeper structure .

The mapping relationship between the array of the heap and the heap structure satisfies ： No i The left child of the first element is the 2*i+1 The elements of , The right child is the number one 2*i+2 The elements of , The parent node is the (i-1)/2 （ Take the whole number ,0 The parent node of bit is itself ） The elements of .

The logical structure of the heap

The physical structure of the heap

 

 2. Large top pile and small top pile

Big pile top That is, for any one in the heap subtree Come on , Of the subtree Maximum It must be its The root node .

Big pile top

Small cap pile That is, for any one in the heap subtree Come on , Of the subtree minimum value It must be Its root node .

Small cap pile

 3. Implementation of related functions of heap structure

This example is a program that can sort the unordered heap into a large top heap , See notes for the meaning of each function .（ The program does not give the main function , If you need to run, please write it yourself ）

/*……………………………………… Heap sort O(logN)………………………………………*/
// The function of heapinsert An overloaded version of 
// Three parameters in this version ,vec Represents an array that is already a large root heap ,size Represents the significant bits in the array ,num For the element to be inserted 
template<typename T>
void heapinsert(vector<T>& vec, int size,T num)
{
	vec.push_back(num);
	while (vec[size] > vec[(size - 1) / 2])
	{
		swap(vec[(size - 1) / 2], vec[size]);
		size = (size - 1) / 2;
	}
	return;
}
// The function of heapinsert An overloaded version of 
// Two parameters in this version ,vec Indicates the heap to be inserted ,size Indicates the significant bit of the heap in this insertion 
template<typename T>
void heapinsert(vector<T>& vec, int size)
{
	while (vec[size] > vec[(size - 1) / 2])
	{
		swap(vec[(size - 1) / 2], vec[size]);
		size = (size - 1) / 2;
	}
	return;
}
// Pile dive 
template<typename T>
void _heapify(vector<T>& vec,int size)
{
	int index = 0;
	int left = index * 2 + 1;

	while (left < size)
	{
		// This sentence is used to judge which child is older , Returns the subscript of the older child 
		//A?B:C The grammar rule of ？ If the previous is true, it returns B False returns C,
		// In this statement, if the right child crosses the boundary , be && The left is false ,？ It was false before , return left;
		// Keep looking back without crossing the line , Judge whether the left and right children are big or small .
		int largest = left + 1 < size && vec[left] < vec[left + 1] ? left + 1 : left;
		if (vec[index] < vec[largest])
		{
			swap(vec[index], vec[largest]);
			index = largest;
			left = index * 2 + 1;
		}
		else
			break;

	}
}
// Pop up maximum 
template<typename T>
T pop_max(vector<T>& vec, int size)
{
	// Swap the top of the heap element with the end of the heap 
	swap(vec[0], vec[size - 1]);
	// Before the end of the heap （ The tail of the heap is not included ） Stack of heapify operation 
	_heapify(vec,size-1);
	return vec[size-1];
}
// Heap sort 
template<typename T>
void heapSort(vector<T>& vec)
{
	if (vec.empty() || vec.size() < 2)
		return;
	// Change the input array into a large root heap 
	for (int i = 0; i < vec.size(); ++i)
		heapinsert(vec,i);
	for (int i = vec.size(); i > 0; --i)
		pop_max(vec, i);
}

Heap sorting is compared with the parent node every time , If it is larger than the parent node, it will float up one layer , Therefore, the maximum number of floats is the number of layers of the heap , Heap is a complete binary tree , According to the properties of complete binary tree, the relationship between the number of layers and the number of elements is 2^h-1,h Is the number of layers , Therefore, the time complexity of heap sorting is O(logn).

Pile dive The meaning of is after taking out the root node of the heap , Sort the remaining nodes to restore them according to the original rules , Its time complexity is also O(logn).

Therefore, a complete unordered heap fetches the maximum value （ minimum value ） The time complexity of is O(2logn), The constant term can be ignored , In the end, it's still O(logn)