[Data Structures] Binary Trees in Nonlinear Tables (Heap Implementation — C Sequential Structures)

=========================================================================

Relevant code gitee self retrieve：

C Learning Diary: Work Harder (gitee.com)

 =========================================================================

follow up on previous period：

[Data Structure Primer] VI. Queues in Linear Tables (Chained Structure Implementation of Queues) – Blogs

 =========================================================================

                     

1 . Tree in a nonlinear table

The concept and structure of trees:

            

Tree concepts

The treeis annonlinear (math.)data structure，
it isby n(n>=0) finite number of nodescreateset with hierarchical relationship。
replantIt’s called a tree.It’s because itIt looks like an upside down tree.That means it’sroot side upbut (not)leaf arrangementThe.
（ jie point：linear structure — joint  ；nonlinear structure — nodal ）
               

Tree structure

• There is aspecial nodeknown asroot noderoot nodeNo predecessor node
               
• except for the root node，Remaining nodesbetenths M(M>0) adisjoint sets T1 、T2 、……、Tm ，
  included among theseEvery collection Ti(1<= i <= m) againA subtree with a structure similar to a tree。
  Root node of each subtreeThere’s one and only one.precursor node，There can be zero or moresuccessor node
                 
• The treeisrecursive (calculation)definethe
               
• tree structureMiddle.There can be no intersection between subtrees，Otherwise it’s not a tree structure

Illustration:

                

Other related concepts of trees:

(Some of the concepts are not well understood in terms of their corresponding meaningsYou can.Look at the following examples in conjunction with the sample diagram)

concept name	equivalent meaning	Example in the figure below
Degree of nodes	anThe node containsthesubtree number call sth (by a name)The degree of this node	Node AThe degree of 6
leaf node (end node)	Degree 0thenodal call sth (by a name)leaf node	Node B、C、H…… is a leaf node
branch node (non-terminal node)	Degree not 0thenodal call sth (by a name) branch node	Node D、E、F…… is the branch node
parent node (parent node)	ifA node contains children， Then this node call sth (by a name)The parent of its children	Node AisNode Bparent of
child node (child node)	a nodeThe root node of the subtree containing call sth (by a name) Children of this node	Node BisNode Achild node of
sibling node	Nodes with the same parent mutually agreed upon sibling node	Node B、Cis a brother node
Tree Degrees	In a tree，The degree of the largest nodecall sth (by a name)Tree Degrees	The tree in the figure belowThe degree of 6
Hierarchy of nodes	Define from the root， The rootforLevel 1(0)，child node of the rootforsecond (i)， in a similar fashion（It is recommended to count from the first level，The empty tree can be represented by the zero level）	Layer where node A is locatedfor the first tier. Layer where node B is locatedFor the second layer ……
Height of the tree (Depth of the tree)	treeMaximum level of a node	The tree in the figure belowThe height (depth) of 4
Cousin Node	parent node(parent node)Nodes in the same layer mutually agreed upon father’s brother’s sons	Node H、Isibling node
Ancestors of nodes	From the root to all the branch nodes on that nodeall forebears	Node Ais the ancestor of all nodes
posterity	Any node in a subtree with a node as root call them all The children of this node	All nodes areNode Adescendant
deforestation	byThe set of m (m>0) trees that do not intersect each other call sth (by a name) deforestation

Example diagram:

                     

                    

---

                    

Tree storage (representation):

                  

Tree representation:

• tree structurecounterpartlinear tableIt’s more complicated.It’s done. It’s done.stockpile（indicate）(after a verb) indicating the beginning and continuation of an action or a stateitmore trouble than it’s worthOh, yeah.
  both… and…Save Value Field，as wellPreserve the relationship between nodes and
                    
• in practiceThe treeThere are many ways to expressAs:
  parental representation、child representation、Child Biparental Representationas well asChild Brother Representationetc.
  We’re right here.A brief look at one of themost commonthe（On the left）kid（right）Fraternization
  （Optimal Design of Tree Structures）
                        

(Left) Child (right) Structure of the brother representation:

The type of data stored in the data fields of each node in the // tree:
                     typedef int DataType;

                     // (left) child (right) brother representation:
                     struct TreeNode
                     {
                         //Data field in the node:
                         DataType data;

                         // First child node -- the leftmost child node:
                         struct TreeNode* firstchild;

                         // Points to the next sibling node of this node -- the right sibling:
                         struct TreeNode* nextbrother;
                     };

                

This representation essentially implements a tree with a linked list:

• firstchild pointer on a gauge — Equivalent topointer to the head of a linked list，Find the head node one level below the current node
                  
• nextbrother pointer on a gauge — Equivalent toChained table traversal pointersYou can.Traverse backward through the nodes of the layer
                   

Use the example chart:

               

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

2 . Binary Tree in Tree

Concept and structure of binary tree:

            

The concept of binary trees

A binary treeisA finite set of nodes，collectionfulfillment：

• orempty
• or byanroot nodeon top of thatTwo trees calledleptotree (math.)andright subtree (math.)thebinary treemake up

             

Structure of a binary tree

• binary treenon-existentNodes with degree greater than 2
  (so)Degree of nodeslikelihoodis0 namely, an empty tree (i.e. not a tree)It could also be1 or2 ）
                   
• Subtrees of a binary treeThere arethe difference between right and left，The order cannot be reversed.ThereforeBinary trees are ordered trees

Illustration:

               

Caution:

with regards toArbitrary binary tree，
allCompounded by the following：

                     

                    

---

                    

Special binary trees

                   

full binary tree (math.)

anbinary treeIfThe number of nodes in each layer is maximizedfollowThis binary tree is a full binary tree。
That is, ifHeight of a binary treefor k andTotal number of nodesbe2^k – 1followIt’s a full binary tree.

Illustration:

                     

                     

complete binary tree (math.)

complete binary tree (math.)isVery efficient data structuresThe complete binary tree isbyfull binary tree (math.)Concepts elicited。
with regards tohigh degreefor K of which there are n nodesthebinary tree，
if and only ifitsEvery nodeallWith a height ofK thefull binary tree (math.)in the numbering from 1 to n The nodes of the one-to-one correspondencewhen
known as…complete binary tree (math.)。
          

Simple to understand.

suppose that…Height of the treebeK ，before K-1 layeris“Full”，
The last layer may not be full.（At least one node), andTree from left to rightisprogressionthe
theThe tree is a complete binary tree

                  

Notes:

full binary tree (math.)isA special kind of complete binary tree

The last layer of a complete binary treesatisfynamelyis a full binary tree

so let’s sayHeight of a complete binary treeforK ，
Highest total number of nodesbe2^K – 1  ；Minimum total number of nodes(The last layer has only one node) is2^(K – 1) 

                 

Illustration:

                     

                    

---

                    

Storage structure of a binary tree

                 

binary treeIt’s generally possible toUse two structures to store，
one kind ofsequential structurekind ofchain structure

              

sequential structure

• sequential structure storagejust likeutilizationarrays to store，
  Any positionBy subscriptingcanFind the father.orkidIn the arrayElement with subscript 0namelyroot node
                 
• Using arrays for storageIt is generally only appropriate to expresscomplete binary tree (math.)（full binary tree (math.)），
  on account ofIf it’s not a complete binary tree there will beWaste of space
                    
• In real life useonly ifThe heap only thenUse arrays to store
                          
• sequential storage in binary treeinphysicallyisAn arrayinlogicallyisA binary tree.
                      

Sequential structural (mathematical) laws:

• pass (a bill or inspection etc)parent node（suffix）locatechild node（suffix）：
  left node  ==》  leftchild  =  parent * 2 + 1
  right node  ==》  rightchild  =  parent * 2 + 2
                 
• pass (a bill or inspection etc)child node（suffix）locateparent node（suffix）：
  parent node  ==》 parent  = (child – 1) / 2
  Observation reveals thatleft node subscriptallodd number，right node subscriptalleven number，
  (even-1) / 2willround down，Get even parent node subscripts，
  the reason whyA formula to find the parent node
                 
• lawonly applicable tocomplete binary tree (math.)Becausecomplete binary tree (math.)It’s continuous from left to right.
  （incomplete binary treeIt is also possible to use theLibyan Arab JamahiriyaBecause nodes are not necessarily consecutive，
  the reason whySome locations in the array do not store elementslead tosquandering of space）

Illustration:

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

3 . Heap in a Complete Binary Tree

Concept and structure of a heap

          

The concept of a heap

If there is aA collection of keycodes   ，
classifier for objects with a handleAll its elementsAccording to theThe sequential storage of a fully binary tree is stored in aone-dimensional arrayIn the，fulfillment：

•  and 

  （ and  ）

  included among thesei = 0，1，2……

thecall sth (by a name)small pile（orlarge amount）

• willLargest heap of root nodesbe known asMaximum stackora big pile of roots—large amount

• Heap with smallest root nodebe known asminimum heaporrootlet— small pile

              

Simple to understand:

small pile— Value of each parent nodeis always less than or equal toThe value of its child node（Value of each child nodeAlways greater than or equal toThe value of its parent node）
large amount — Value of each parent nodeAlways greater than or equal toThe value of its child node（Value of each child nodeis always less than or equal toThe value of its parent node）

              

Structure of the heap

• The value of a node in the heapAlways no greater or no less thanThe value of its parent node
                
• The heapalwaysA complete binary tree

Illustration:

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

4 . Heap implementation

Implementing a Heap Using the Sequential Structure of a Binary Tree

• Ordinary binary treeandunsuitablearrays（sequential structure）to storeBecauseThere will be a lot of wasted space
               
• whilecomplete binary tree (math.)moreserviceabilitysequential structurestockpile，
  the reason whyIn reality, it is common to putThe heap（A complete binary tree）utilizationArrays of sequential structuresto store
                  
• needattention (heed)Yes.Here’s the heapandHeap in the address space of an operating system virtual processtwo quite different things，
  one isdata structure，one isA segment of an area of the operating system that manages memory
                   

(Detailed explanations are in the notes to the pictures, and the code subfile is placed under a heading)

                             

Preparation for the realization of specific functions

• instack header fileIncludes the header files required afterward
                
• definenodal value(bottom-of-heap array element(used for emphasis)typology
                
• Defining Heap Types

icon

            

            

———————————————————————————————

            

HeapInit function — initializes members of the heap type

• assertReceived heap type pointer is not null
                 

• willHeap root pointerSet to NULL，
  generalCurrent number of nodes in the heapSet to 0，
  generalSpace units currently opened by the heapSet to 0

icon

            

            

———————————————————————————————

            

HeapDestroy function — performs destruction on the heap type

• assertReceived heap type pointer is not null
                 

• liberate (a prisoner)Dynamic space in the heap type opened with a as header
                

• willCurrent number of nodes in the heapandSpace units currently opened by the heapSet to 0

icon

            

            

———————————————————————————————

            

HeapPrint function — prints the value of each node in the heap

• assertReceived heap type pointer is not null
                 

• utilizationfor loopcyclic printing

icon

            

            

———————————————————————————————

            

Swap function — swaps node positions in an up-down adjustment operation.

• upward adjustment（AdjustUp Internal Functions(math.) andDownward Adjustment（AdjustDown internal function）isin
  push in a node（HeapPush function(math.) andHeap Deletion Nodes（HeapPop）Important steps in the operation，
  (indicates contrast)inAdjustment upward operationandDownward Adjustment OperationIn therequireSwap function，Exchanging two node values
                 

• The function is simple to implement.Create a temporary variable to swap the two node values.can immediately (do sth)

icon

            

            

———————————————————————————————

            

AdjustUp Internal Functions
—
Used to adjust the position of a node in the heap upwards after it has been inserted (HeapPush function)

• pass (a bill or inspection etc)on top of“sequential structure”The formulas taught in
  pass (a bill or inspection etc)Subnode subscript childlocateIts parent node subscript parent
                 

• utilizationwhile loopMake upward adjustments

icon

            

            

———————————————————————————————

            

(Hard) HeapPush function — inserts a node into a heap type

• assertReceived heap type pointer is not null
                 

• post assertionDetermine if capacity expansion is needed，failing agreementPerform capacity expansion operationsandCheck if the expansion is successful
                

• After enough space，Putting the inserted node into the heap
  insertedCurrent number of nodes in the heap size++
                  

• After inserting a nodecall (programming) upward adjustmentAdjustUp Internal Functions，
  Adjustment of the position of the inserted node in the heap，
  feasibleThe whole thing is still a heap after insertion（Large or small piles）

icon

            

            

———————————————————————————————

            

HeapInitArray function — takes an array and initializes it to a heap base array.

• realizationtheUpward Debugging AdjusuUp Internal FunctionsLater.
  canUse it to build piles（It’s up to you whether you build a big pile or a small one.within AdjustUp functioncondition setting），
  compared with the previoustheHeapInit initialization function，
  This function willOpen dynamic space directly for the heapmergePut in the values of each node
                 

• assertReceived heap type pointer is not null
  assertArray a is not empty
                

• Opening up dynamic spacesandInspection of openings
                  

• willCurrent number of nodes in the heapSet to n
  generalSpace units currently opened by the heapSet to n
                      

• willElements of array aCopy as heap bottom array element
                 
• againcirculateupward adjustmentNodes in the heap（underlying array element）Perform pile building

icon

            

            

———————————————————————————————

            

AdjustDown internal function
—
Used to adjust the heap downward after removing the root node (HeapPush function) so that it is still a heap

• pass (a bill or inspection etc)on top of“sequential structure”The formulas taught in
  pass (a bill or inspection etc)The parent node subscript parentlocateIts left child node subscript child
                 

• utilizationwhile loopCycle down the adjustment heap（Take a small pile as an example）
                

• inwhile looppriorfind outThe current two children of thesubscript of a smaller child node
                  

• inwhile loop，After finding the smaller node subscript，
  Determine if a downward adjustment is required，execute the corresponding operation

icon

            

            

———————————————————————————————

            

(Difficult) HeapPop function — removes the root node of the heap type (removes the most current value in the heap)

• assertReceived heap type pointer is not null
  assertNumber of heap nodes（Number of elements in the underlying array）Not 0
                 

• utilizationSwap node Swap functionSwap the root node value with the tail node value
  deutero-Remove the original root node that was moved to the end.
                

• utilizationAdjustDown internal functionDownward adjustment of the heap

icon

            

            

———————————————————————————————

            

HeapTop function — gets and returns the push root node value

• assertReceived heap type pointer is not null
  assertNumber of heap nodes（Number of elements in the underlying array）Not 0
                 

• straightforwardReturns the root node value

icon

            

            

———————————————————————————————

            

HeapEmpty function — determines whether the heap type is empty or not

• assertReceived heap type pointer is not null
                 

• in the event thatNumber of heap nodes（Number of elements in the underlying array）A value of 0 indicates that the heap is empty

icon

            

            

———————————————————————————————

            

Overall test:

            

            

———————————————————————————————

            

HeapSort sort function (hard)
—
Sorting ordinary arrays (ascending or descending) using downward-adjusting operations in the heap

• build up a pile：
  The array to be sortedThink of it as a complete binary tree.，
  utilizationLoop down adjustment operationFrom the penultimate parent node（non-leaf node）Beginning of downward adjustment，
  After completion of adjustments，arrayswouldConsistent with the nature of a heap(Here’s an example of a small pile)
  ascending order —create a big pile        ；        descending order — create a small pile
                 

• arrange in order：
  utilizationwhile loopsort，
  classifier for objects with a handleminimum value（root node of a small heap(math.) andtail elementcarry out an exchange，
  theValues other than the minimumlook upon as a pilecarry outDownward Adjustment，Selection of sub-size values，
  settheLast value，Loop again to adjust the next

icon

                

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

                

5 . Corresponding code

Heap.h — header file

#pragma once

// Include the required header files afterward in the heap header file:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>


// Define the type of the node value (the array element at the bottom of the heap):
typedef int HPDataType;

// Define the heap type:
typedef struct Heap
{
	// Because the underlying implementation is in a sequential structure.
	// So the type is similar to a sequential table:

	// Pointer to a heap node:
	// (points to the first element of the array at the bottom of the heap)
	HPDataType* a;

	// The current number of nodes in the heap:
	// (number of elements in the array at the bottom of the heap)
	int size;

	// The unit of space currently opened by the heap:
	// (units of space dynamically opened by the array at the bottom of the heap)
	int capacity;

}HP; // Heap type Heap renamed to HP



// heap initialization function 1 -- initializes members of the heap type
// Receive pointer to heap type (php)
void HeapInit(HP* php);

// Heap Destruction Functions -- Destruction of Heap Types
// Receive pointer to heap type (php)
void HeapDestroy(HP* php);

// Print the heap function -- prints the values of the nodes in the heap.
// Receive pointer to heap type (php)
void HeapPrint(HP* php);

// Node Position Swap Function -- Swaps node positions in an up-down adjustment operation:
// Receive pointers to the two nodes to swap places (p1 and p2)
void Swap(HPDataType* p1, HPDataType* p2);

// Heap insertion function -- inserts a node into a heap type
// Receive pointer to heap type (php)和插入节点的值（x）
void HeapPush(HP* php, HPDataType x);

// Heap Initialization Function 2 -- Receives an array to initialize it to a heap base array.
// Receive pointer to heap type (php)、数组首元素地址（a）、数组元素个数（n）
void HeapInitArray(HP* php, int* a, int n);

// Heap Delete Function -- Deletes the root node of the heap type (deletes the most current value in the heap)
// Receive pointer to heap type (php)
void HeapPop(HP* php);

// top-of-heap function -- gets and returns the push root node value
// Receive pointer to heap type (php)
HPDataType HeapTop(HP* php);

// Empty function -- determines if the heap type is empty.
// Receive pointer to heap type (php)
bool HeapEmpty(HP* php);

            

            

———————————————————————————————

                

Heap.c — implementation file

#define _CRT_SECURE_NO_WARNINGS 1
// Contains the heap header file:
#include "Heap.h"
// heap initialization function 1 -- initializes members of the heap type
// (no value is given at first, then a function is used to insert values to form a heap)
// Receive pointer to heap type (php)
void HeapInit(HP* php)
{
//assert asserts that the received heap type pointer is not null:
// (Ensure that there is successful creation of heap types that can be initialized)
assert(php);
// Set the heap root node pointer to NULL:
php->a = NULL;
// Set the number of current nodes of the heap to 0:
php->size = 0;
// Set the heap's current unit of open space to 0:
php->capacity = 0;
}
// Heap Destruction Functions -- Destruction of Heap Types
// Receive pointer to heap type (php)
void HeapDestroy(HP* php)
{
//assert asserts that the received heap type pointer is not null:
// Ensure that there are heap types that can be destroyed
assert(php);
// Free the dynamic space in the heap type opened with a as the header:
free(php->a);
// Set the current number of nodes in the heap and the current unit of space opened by the heap to 0:
php->a = NULL;
php->size = php->capacity = 0;
}
// Print the heap function -- prints the values of the nodes in the heap.
// Receive pointer to heap type (php)
void HeapPrint(HP* php)
{
//assert asserts that the received heap type pointer is not null:
// (Make sure there is a successful creation of a heap type that can be printed)
assert(php);
// Loop printing using a for loop:
for (int i = 0; i < php->size; i++)
//size prints as many node values as there are nodes:
{
// Print node values by subscript:
printf("%d ", php->a[i]);
}
// Line breaks:
printf("\n");
}
// Node Position Swap Function -- Swaps node positions in an up-down adjustment operation:
// Receive pointers to the two nodes to swap places (p1 and p2)
void Swap(HPDataType* p1, HPDataType* p2)
{
// Create a temporary variable to cooperate in swapping the two node values:
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// Implement an externally undeclared AdjustUp function internally.
// The first parameter receives the address of the first element of the bottom array of the heap.
//Second parameter receives the subscript of the just inserted array element (child node).
void AdjustUp(HPDataType* a, int child)
{
//Using the formulas mentioned earlier.
// Find the parent node subscript by its child node subscript:
int parent = (child - 1) / 2;
// Continue to adjust upwards as long as child is still greater than 0
// The subscripts of the upper nodes are smaller if they need to be adjusted upwards.
// So the child keeps getting smaller and smaller as it adjusts.
while (child > 0)
{
// Upward adjustment in small stacks:
if (a[child] < a[parent])
//Smaller heap with child node values smaller than the parent node values::
// In the big heap then the condition is changed to:
//if (a[child] > a[parent]) //upward adjustment for large piles
{
//Then the two would need to be switched.
Swap(&a[child], &a[parent]); 
After //Value substitution is successful, the subscripts are also adjusted:
//child is subscripted to parent subscript after moving to the upper level:
child = parent;
//child may also be a child of a parent node further up the hierarchy after it is moved to that level.
// It may need to be adjusted upwards again, at worst moved to become the root node of the heap:
// Get the subscript of the new parent again:
parent = (parent - 1) / 2;
}
else
// If the value of the child node in the mini-heap is already greater than or equal to the value of the parent node
//that is, it qualifies as a small heap
{
// Then there is no need to make upward adjustments, break exits the loop:
break;
}
}
}
// Heap insertion function -- inserts a node into a heap type
// Receive pointer to heap type (php)和插入节点的值（x）
void HeapPush(HP* php, HPDataType x)
{
//assert asserts that the received heap type pointer is not null:
// Make sure there are heap types to insert nodes into
assert(php);
// Check if expansion is needed after assertion:
if (php->size == php->capacity)
//Number of current nodes in the heap == units of open space.
//State that expansion is required before inserting a node:
{
// Create a variable to store the new capacity unit:
int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
// Because capacity is initialized to 0, it can be augmented using the trinomial operator:
//ps->capacity == 0 ? 4 : ps->capacity * 2
// if 0 then directly increase capacity to 4, if not 0 then increase capacity 2 times
// Open up dynamic space:
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
// Here the realloc function is used directly for dynamic space opening.
// If the realloc function receives the header pointer (the first argument to the function) as null, the
// Then it is equivalent to the malloc function
//Checks on opening space:
if (tmp == NULL)
// Returns a null pointer and fails to open:
{
// Print the error message:
perror("realloc fail");
// Terminate the program:
exit(-1);
}
//After successfully opening the space, assign the header pointer of the opened space to a:
php->a = tmp;
// Assign the new capacity unit to the original capacity unit:
php->capacity = newCapacity;
}
// Perform insertion operations in the heap:
// Heap:
// Physical structure is an array; logical structure is a tree.
//Tree would have no concept of header and tail plugs
//Where exactly the node is inserted depends on the situation
// As long as the inserted value is large enough or small enough, you can keep replacing it one level up
//nodes inserted into the heap are to remain still a heap, a tree continuous from left to right
// Whatever the case, default to inserting the very end first:
// (i.e., the end of the array at the bottom of the heap)
// because the array subscripts start at 0.
// So size is the end insertion node subscript:
php->a[php->size] = x;
// Number of current nodes in the heap after insertion size++:
php->size++;
// At this point, if the insertion node is large enough (or small enough), the
// then the condition for a large (or small) heap is just satisfied, the
// but if it is not satisfied, adjust the insertion node towards the upper level of the tree, the
// and that it will be performed again afterwards.
// So here you can define an AdjustUp function inside the file.
// and make the call:
AdjustUp(php->a, php->size-1);
// The first parameter receives the address of the first element of the bottom array of the heap.
//Second parameter receives the subscript of the just inserted array element (child node).
// php->size-1 -- size++ after insertion of nodes in front of it
// So the subscript here should be -1 to get the subscript of the inserted element.
}
// Heap Initialization Function 2 -- Receives an array to initialize it to a heap base array.
// (gives you the individual values of the underlying array, which are then adjusted upwards to form the heap)
// Receive pointer to heap type (php)、数组首元素地址（a）、数组元素个数（n）
void HeapInitArray(HP* php, int* a, int n)
{
//assert assert asserts that the received heap type pointer is not null:
// (Ensure that there is successful creation of heap types that can be initialized)
assert(php);
//assert asserts that the array a is not empty:
assert(a);
// Open up dynamic space:
php->a = (HPDataType*)malloc(sizeof(HPDataType*) * n);
//Checks on opening space:
if (php->a == NULL)
// Returns a null pointer and fails to open:
{
// Print the error message:
perror("realloc fail");
// Terminate the program:
exit(-1);
}
// Set the number of current nodes of the heap to n:
php->size = n;
// Set the unit of space currently opened by the heap to n:
php->capacity = n;
// Make a copy of the array element as a heap bottom array element:
memcpy(php->a, a, sizeof(HPDataType) * n);
// Re-loop to adjust the nodes in the heap (the underlying array elements) upwards to build the heap :
for (int i = 1; i < n; i++)
{
AdjustUp(php->a, i);
}
}
// Implement an internally undeclared AdjustDown function.
// The first parameter receives the address of the first element of the bottom array of the heap.
// The second parameter receives the number of heap nodes (the number of elements in the underlying array).
//The third parameter receives the subscript of the root node (the original tail node) after the swap.
void AdjustDown(HPDataType* a, int n, int parent)
{
//(In small heaps) downward adjustments are needed to get child nodes that are smaller than the parent parent:
// (This child node should be switched with its parent)
// You can start by assuming that the left child node is smaller than the parent:
// Get the left child (first child) subscript of the root node:
int child = parent * 2 + 1;
// Worst case: root node becomes a leaf (no more children to replace)
while (child < n)
// left child node subscript if >= number of heap nodes (number of underlying array elements)
//Indicates that the array is out of range, and the parent node has become a leaf and can no longer be switched.
{
//If we are wrong in our assumptions above:
if (child + 1 < n  &&  a[child + 1] < a[child])
// In the big heap then the condition is changed to:
//if (child + 1 < n && a[child + 1] > a[child]) //downward adjustment for large piles
// child+1 is the subscript of the right child.
/* Compare the smaller node only if both left and right children exist:	
Prevent non-existent right child nodes from crossing boundaries: child + 1 < n
The above can enter the while loop as long as the left child node is in the array
And the left child node is probably the last element of the array
It may happen that the left child node exists but the right child node does not exist
So to compare smaller nodes in the presence of right child nodes
/No right child node directly uses the left child node.
*/
// If the right child node is smaller than the left child node:
{
// To get the right child node (smaller child node) subscript:
++child; // self-incremented, i.e., right child node subscripts
}
// Get the subscript of the smaller node by this point:
// (doesn't care if it's a left or right child node, just the node with the smaller value)
// (in a small heap) if the smaller node is smaller than the parent node
if (a[child] < a[parent])
// In the big heap then the condition is changed to:
//if (a[child] > a[parent]) //downward adjustment of large heaps
{
// Then the two need to be switched:
Swap(&a[child], &a[parent]);
// After swapping the two node values, the subscripts should also be refreshed:
parent = child;
// At this point the new child node is subscripted:
child = parent * 2 + 1;
}
else
// If the smaller node is already larger than the parent:
{
// That qualifies as a small pile, no need to switch:
break; //exit the loop
}
}
}
// Heap Delete Function -- Deletes the root node of the heap type (deletes the most current value in the heap)
// Receive pointer to heap type (php)
void HeapPop(HP* php)
{
//assert asserts that the received heap type pointer is not null:
// Ensure that there are heap types available to delete the root node
assert(php);
//assert asserts that the number of heap nodes (the number of underlying array elements) is not zero.
// Ensure that there are nodes available for deletion:
assert(php->size > 0);
/*
If a move is made to overwrite the root node of the first position
It will cause the remaining node relationships to be messed up (brother to father to son)
The end result may not always be a heap that
And moving overrides in arrays is inherently inefficient
So it is possible to swap the root and tail nodes
A further tail deletion realizes the deletion of the root node
and the tail deletion in the array is more efficient.
*/
// Swap the root node value with the tail node value:.
Swap(&php->a[0], &php->a[php->size - 1]);
// &php->a[0] : root node value
// &php->a[php->size - 1] : tail node value
// Then delete the original root node that was moved to the end:
--php->size; // just direct the number of elements size-1
/*
At this point the structure of the left and right subtrees of the heap remains unchanged
Left and right subtrees are still small piles (big piles)
With this premise downward adjustments can be made:
Because the root and tail nodes swap places in front
So now the root node (the original tail node) may have to be larger than the starting child node
The tree as a whole does not qualify as a small heap, so a downward adjustment is made
(Note: Upward adjustment assumes that the preceding node qualifies as a heap)
Adjust the operation downward:
After becoming a root node, compare it with its two children
If the child nodes are smaller, swap positions
Swap positions and then compare with the next level of child nodes
If the child nodes are smaller, swap positions
And so on, at worst until it becomes a leaf
(Larger values in the smaller pile move down, smaller values go up)
*/
// So here you can define a downward adjustment function AdjustDown inside the file.
// and make the call:
AdjustDown(php->a, php->size, 0);
// The root node is subscripted 0 in the underlying array
/*
* :: Meaning and examples of the function:
The meaning of this function is to remove the first smallest value (in a small heap)
Then find the second smallest value, and so on, you can find the smallest value of the array in turn
Example: "Top 10 cake stores in the city" Small pile of root elements on the first good store that
Find the second best store after using this function and so on ......
*/
/*
* Time complexity of the function:
The downward or upward adjustment operation is performed 1 time in the best case and the height of the tree in the worst case.
I.e., time complexity is O(logN), and a billion values need to be adjusted only 30+ times -- excellent!
(log -- defaults to 2)
*/
}
// top-of-heap function -- gets and returns the push root node value
// Receive pointer to heap type (php)
HPDataType HeapTop(HP* php)
{
//assert asserts that the received heap type pointer is not null:
// Ensure that there is a heap type available to get the root node value
assert(php);
//assert asserts that the number of heap nodes (the number of underlying array elements) is not zero.
// Make sure there are nodes in the heap type:
assert(php->size > 0);
// Return the root node value directly:
return php->a[0];
}
// Empty function -- determines if the heap type is empty.
// Receive pointer to heap type (php)
bool HeapEmpty(HP* php)
{
//assert asserts that the received heap type pointer is not null:
// Ensure that there is a heap type available to get the root node value
assert(php);
// If the number of heap nodes (number of elements in the underlying array) is 0 then the heap is empty:
return php->size == 0;
//php->size = 0 -- establishment returns true, heap is empty
//php->size = 0 -- return false if not true, heap is not empty 
}

            

            

———————————————————————————————

                

Test.c — test file

#define _CRT_SECURE_NO_WARNINGS 1
// Contains the heap header file:
#include "Heap.h"
// Test function -- unordered
void Test0()
{
//Create an array to create the values of the nodes to be placed in the heap.
int a[] = { 65,100,70,32,50,60 };
// Calculate the length of the array:
int alength = sizeof(a) / sizeof(int);
// Create a heap type variable:
HP hp;
// Initialize using the HeapInit function:
HeapInit(&hp);
// Use a for loop to put each value of the array into a heap type variable:
for (int i = 0; i < alength; i++)
{
// The heap type variable hp is just a full binary tree before there is a HeapPush.
// after insertion and sorting with the HeapPush function it becomes a heap.
// So one way to build a heap is to always push:
// Insert nodes using the HeapPush function:
HeapPush(&hp, a[i]);
}
printf("Current Heap:> ");
// Print the heap using the HeapPrint function:
HeapPrint(&hp);
// Use the HeapEmpty function to determine if the heap is empty:
while (!HeapEmpty(&hp))
// Get the heap root node value if it is not null:
{
// Use the HeapTop function to get the heap root node value and print it:
printf("Current heap root value: > %d\n", HeapTop(&hp));
//(in a small heap) using the HeapPop function to delete the current root node.
// and set the second smallest node as the new root node:
HeapPop(&hp);
}
// Destroy using the HeapDestroy function:
HeapDestroy(&hp);
}
Test function -- sorting
//
Heap sort function (before optimization) - sorts a normal array (ascending or descending) using the heap type
First parameter: address of the first element of the array at the bottom of the heap.
Second parameter: the number of elements in the bottom array of the heap.
//void HeapSort(int* a, int n)
//{
//	// Create a heap type variable:
//	HP hp;
//
//	// Initialize using the HeapInit function:
//	HeapInit(&hp);
//
//	// Use a for loop to put each value of the array into a heap type variable:
//	for (int i = 0; i < n; i++)
//	{
//		// The heap type variable hp is just a full binary tree before there is a HeapPush.
//		// after insertion and sorting with the HeapPush function it becomes a heap.
//		// So one way to build a heap is to always push:
//
//		// Insert nodes using the HeapPush function:
//		HeapPush(&hp, a[i]);
//	}
//
//	//printf("Current Heap:> ");
// Print the heap using the HeapPrint function:
//	//HeapPrint(&hp);
//
//	int i = 0;
//	// Use the HeapEmpty function to determine if the heap is empty:
//	while (!HeapEmpty(&hp))
//		// Get the heap root node value if it is not null:
//	{
//// (in a small heap) Assign the root node value of the heap type to the array a, in order.
//// Use the heap implementation to sort the array from smallest to largest:
//		a[i++] = HeapTop(&hp);
//
//		//(in a small heap) using the HeapPop function to delete the current root node.
//		// and set the second smallest node as the new root node:
//		HeapPop(&hp);
//	}
//
//	// Destroy using the HeapDestroy function:
//	HeapDestroy(&hp);
//}
Flaws in this sorting:
1. There has to be a heap data structure first.
2. Consumption of space complexity
//void Test1()
//{
//// Create a heap bottom array -- node values are randomized; unsorted
//	int a[] = { 65,100,70,32,50,60 };
//
//	// Calculate the length of the array:
//	int alength = sizeof(a) / sizeof(int);
//
// printf("Array before applying heap sort:> ");
//// Apply the array before the heap sort:
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	printf("\n");
//	
//// Use the HeapSort function to sort the unsorted array at the bottom of the heap:
//	HeapSort(a, alength);
//
// printf("Array after applying heap sort:> ");
//// Apply a heap-sorted array:
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//
//}
Test function -- sorting
//
Heap sort function (optimized) - sorts a normal array (ascending or descending) using heap type ideas
First parameter: address of the first element of the array at the bottom of the heap.
Second parameter: the number of elements in the bottom array of the heap.
//void HeapSort(int* a, int n)
//{	
//// Previously after creating the heap type using the HeapPush function.
//// Re-applied to sorting ordinary arrays, the
//// Then we can do without the heap, too.
//// Use the HeapPush function directly along the lines of building ordinary arrays into heaps:
//	
//// Adjust upward to build a heap -- time complexity -- O(N*logN)
//// Think of the array as a fully binary tree and then build the heap:
//// In AdjustUp you can set whether the adjustment is a big or small stack adjustment.
//	for (int i = 1; i < n; i++)
//// Sorting from the second element of the array (subscript 1), with the first element defaulting to the root node, the
//// Further adjustments are made after using the AdjustUp function:
//	{
//// Previously the AdjustUp adjustment function was used for heap type operations.
//// The AdjustUp adjustment function can also be used here on normal arrays.
//// It's just that heap types need to be expanded, whereas normal arrays don't.
//// Resize the normal array as a large or small heap:
//		AdjustUp(a, i);
//	}
//
//// Now the first element is equivalent to the (small heap) root node, i.e., the minimum value
//// To pick the next smallest value again, you can only look at the remaining data as a heap
//// But the parent-child relationship is all messed up, and the remaining data is not necessarily still a heap
//// It's possible to rebuild the heap again, but it's too expensive.
//
//// Another thought: ascending order (from smallest to largest) with large heaps
//// Build the array into a big heap, and after picking out the maximum value, swap the maximum value with the most trailing value
//// so that in ascending order (from smallest to largest) a value is also lined up, i.e. the largest value is placed at the end
//// Then look at the other values except the largest value as a heap and adjust downward to select the next largest value
//// Put in the penultimate position and loop through the set -- time complexity NlogN
//// (by the same token, use a small heap if it's in descending order (largest to smallest))
//
//// In descending order (from largest to smallest) using a small heap as an example:
//
//// Get the array tail element subscript first:
//	int end = n - 1;
//// Sorting using a while loop:
//	while (end > 0)
//// The subscript of the end element of the array is greater than indicating that there are at least two more elements, continue sorting:
//	{
//// Swap the minimum (the root node of the small heap) with the tail element:
//		Swap(&a[0], &a[end]);
//
//// Look at all but the smallest value as a heap and do a downward adjustment to pick the next largest value:
//		AdjustDown(a, end, 0);
//// end is the value other than the minimum (the first n-1 values of the array)
//
//// This adjusts the tailmost value, and the end-1 loop adjusts the next one:
//		end--;
//	}
//  
//}
//
//void Test2()
//{
//// Create a heap bottom array -- node values are randomized; unsorted
//	//int a[] = { 75,65,100,32,50,60 };
//	int a[] = { 2,3,5,7,4,6,8 };
//
//	// Calculate the length of the array:
//	int alength = sizeof(a) / sizeof(int);
//
// printf("Array before applying heap sort:> ");
//// Apply the array before the heap sort:
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	printf("\n");
//
//// Use the HeapSort function to sort the unsorted array at the bottom of the heap:
//	HeapSort(a, alength);
//
// printf("Array after applying heap sort:> ");
//// Apply a heap-sorted array:
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//
//}
//Test function -- sorting
// Heap sort function (re-re-optimized) -- sorts ordinary arrays (ascending or descending) using only downward adjustments
//First parameter: address of the first element of the array at the bottom of the heap.
//Second parameter: the number of elements in the bottom array of the heap.
void HeapSort(int* a, int n)
{
// downward-adjusted build heap -- time complexity: O(N)
//Think of the array to be sorted as a complete binary tree.
// Adjust downward from the penultimate first parent (non-leaf node):
for (int i = (n-1-1)/2; i >= 0; i--)
//(n-1-1)/2 -- n-1 is the subscript of the last leaf, which -1 then /2 (Eq.)
//find its parent node (the penultimate parent node), adjust that parent node after i--
// Adjust the previous parent again until it adjusts down to the root node
{
AdjustDown(a, n, i); //adjust downward from position i
}
//worst-case number of executions to build the heap: T(N) = N - log(N+1)
// Thus: the time complexity of building a heap is O(N)
// Start sorting: in descending order (largest to smallest) using a small heap as an example:
// Get the array tail element subscript first:
int end = n - 1;
// Use a while loop for sorting:
while (end > 0)
//The subscript of the end element of the array is greater than indicating that there are at least two more elements, continue sorting:
{
// Swap the minimum (root node of the mini-heap) with the tail element:
Swap(&a[0], &a[end]);
// Look at all but the smallest value as a heap and adjust downward to pick the next largest value:
AdjustDown(a, end, 0);
//end is the value other than the minimum value (the first n-1 values of the array)
// This adjusts the tail-most value, and the end-1 loop adjusts the next one:
end--;
}
}
void Test3()
{
// create a heap bottom array -- node values randomized; unsorted
//int a[] = { 75,65,100,32,50,60 };
int a[] = { 2,3,5,7,4,6,8 };
// Calculate the length of the array:
int alength = sizeof(a) / sizeof(int);
printf("Array before applying heap sorting:> ");
// Apply the array before the heap sort:
for (int i = 0; i < alength; i++)
{
printf("%d ", a[i]);
}
printf("\n");
// Use the HeapSort function to sort the unsorted array at the bottom of the heap:
HeapSort(a, alength);
printf("Array after applying heap sorting:> ");
// Apply the heap-sorted array:
for (int i = 0; i < alength; i++)
{
printf("%d ", a[i]);
}
}
// Main function:
int main() 
{
//Test0();
//Test1();
//Test2();
Test3();
return 0;
}