2022-02-11 heap sorting and recursion

Abstract :

Record the experience when sorting the research reactor .

Heap sort :

Heap sorting is also a sort based on comparison , But its ideological basis comes from recursion , This is very significantly different from the idea of partition .

As a classic embodiment of recursive thought , It is necessary to draw lessons from the process of heap sorting .

Pseudo code for heap sorting :

CLRS

End of recursion , The key point is in the eighth line , Only when the subscript of the found maximum value is not itself , Before continuing recursion .

If you are the largest between yourself and the left node and the right node , Then recursion stops .

need MAX-HEAPIFY Only for a single node , Not the whole heap , So recursive calls are needed for the whole heap MAX-HEAPIFY

TAOCP This is the process in

Heap sort analysis :

Think about it as a whole , Then heap sorting can be abstracted into , A node , Dealing with the relationship between its left node and right node .

Start from the top , Then each point and its left and right nodes are processed recursively .

Consider starting from the top , Then pile top node , It is limited to the smallest data node of the whole heap

-> The heap top must be smaller than its left and right child nodes .

-> The left and right child nodes of the heap top , It must be smaller than the left and right child nodes of the corresponding node