I realize large top stack with C I

One 、 The realization of the heap

1. Heap structure ：

      The logical structure is similar to A tree “ Trees ”

 

 

2. Type of heap ：

    Large top pile structure ： A special kind of tree ： Each child node is smaller than the parent node

    Small top pile structure ： Empathy ： Each child node is larger than the parent node

Structure diagram ：

2. Big pile top Code implementation ：（ Here we implement heap Use a sequential table ）

   ① initialization ：

typedef int Heaptype;

typedef struct Heap
{
	Heaptype* head;   
	int size;         // Record the total heap capacity  
	int capacity;     // Record the total number of current data 
}Heap;

// Initialization of the heap 
void Heap_Init(Heap* pphead)
{
	assert(pphead);
	pphead->head = NULL;
	pphead->size = 0;
	pphead->capacity = 0;
}

② insert data ：

  Implementation details ： Data is inserted at the same time , Adjust the data structure , Keep the maximum number of tree tops at all times

                  If the newly inserted node is larger than the parent node , To exchange , Therefore, this link of structural adjustment is independent

                  namely ：“ Adjust up ”.

  Adjust up ： Because when inserting data ： New data is stored at the end of the sequence table by default , Therefore, it is logically at the bottom of the heap ,

                  therefore , When the new data is larger than the parent node , It will swap with the parent node that is logically above it , be called

                  Adjust up .

notes ： Upward adjustment sometimes more than once , It may also be adjusted many times , Until each node is in its corresponding position .

  Flow chart ：

Big top pile insertion process

Minutiae ： Because the data is stored in a sequential table , Therefore, the subscript of the child node is consistent with that of the parent node

              The formula ：parent = (child - 1)/2 ;( It will be understood when the calculation is carried out according to this formula ) 

// Adjust up 
void adjust_up(Heap* pphead)
{
	int child = pphead->capacity;
	int parent = (child - 1) / 2;
	for (; pphead->head[parent] < pphead->head[child];)// Judge whether it conforms to the big top pile 
	{
		swap(&(pphead->head[parent]),&(pphead->head[child]));// swapping 
		child = parent;
		parent = (child - 1) / 2;
	}
}

// insert data 
void Heap_push(Heap* pphead, Heaptype data)
{
	assert(pphead);
    // Judge whether the capacity is full and expand 
	Heap_realloc(pphead);
	pphead->head[pphead->capacity] = data;
    // Adjust up 
	adjust_up(pphead);
	pphead->capacity++;
}

③ Delete data ： To avoid disrupting the structure of the whole heap by directly deleting the header data ,

Here, first exchange the header data and tail data , Then delete the tail data , Then use “ Downward adjustments ”, namely ： Compare and adjust the replaced top data downward with its child nodes , Until it conforms to the large top pile structure .

    notes ：1. When the big top stack is adjusted downward , The parent node should exchange with the larger of the two child nodes , So compare .

          2. The calculation formula of subscript here is ： Left the child ：child = (parent * 2) + 1

                                                  The right child ：child = (parent * 2) + 2

          3. Avoid crossing boundaries when calculating child subscripts , Avoid comparing the parent node with data that does not belong to the heap .

// Delete data 
void Heap_pop(Heap* pphead)
{
	assert(pphead);
	assert(pphead->capacity > 0);      // Prevent the heap from being empty 
    // Exchange top data with tail data 
	swap(&(pphead->head[0]),&( pphead->head[pphead->capacity-1]));
	pphead->capacity--;
    // Downward adjustments 
	adjust_down(pphead,0);
}

// Downward adjustments 
void Adjust_down(int* a, int size, int parent)
{
	assert(a);
	for (int child = parent * 2 + 1; child <= size; child = parent * 2 + 1)
	{
        // By default, the left child paper is used to compare with the parent node , If the right child paper is larger than the left child paper and does not cross the boundary, exchange 
		if (a[child] > a[child + 1] && child + 1 <= size)
			child = child + 1;
        // Compare child paper and parent node 
		if (a[child] < a[parent])
		{
			int temp = a[child];
			a[child] = a[parent];
			a[parent] = temp;
		}
        // Continue to compare downward 
		parent = child;
	}
}

④ Capacity expansion || Sentenced to empty || Top data || Destroy the pile

// Judge whether to expand capacity 
void Heap_realloc(Heap* pphead)
{
	assert(pphead);
	if (pphead->size == pphead->capacity)
	{
		Heaptype Newsize = (pphead->size == 0) ? 4 : (pphead->size * 2);
		Heaptype* Newhead = (Heaptype*)realloc(pphead->head,sizeof(Heaptype) * Newsize);
		if (Newhead == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		pphead->head = Newhead;
		pphead->size = Newsize;
	}
}

// Determine whether the heap is empty 
bool Heap_Empty(Heap* pphead)
{
	if (pphead->capacity)
		return false;
	return true;
}
// Take the top data 
Heaptype Heap_top(Heap* pphead)
{
	return pphead->head[0];
}
// Destroy the pile 
void Heap_Destory(Heap* pphead)
{
	assert(pphead);
	free(pphead->head);
	pphead->head = NULL;
	pphead->size = 0;
	pphead->capacity = 0;
}

Thank you for your visit ！！！