[Data structure: Heap] Large root heap, small root heap, heap upward adjustment algorithm, downward adjustment algorithm and heap function implementation!

Foreword

This series of articles [Data Structure] will use C/C++ for design and implementation by default! For implementation methods in other languages, please refer to the analysis and design ideas to implement it yourself!

Note[1]: The article is a study summary and does not have the corresponding sequence compared to the textbook! (You can check whether the corresponding article exists in the collection)!
Note[2]: If you have any questions or want the blogger to analyze the content, you can send a private message in the background!

Article directory

  • Preface
  • Understanding of complete binary trees
  • Basic understanding of heap
  • The nature of the heap and the size of the root heap [Important]
  • The structure of the heap and its sequential structure (features)
    • Understanding the structure of the heap
    • sequential storage structure
  • Adjust the algorithm upwards
    • Basic idea of the algorithm (taking small root heap as an example):
    • C/C++ language code design
  • Adjust algorithm downwards
    • Basic idea of the algorithm (taking the large root heap as an example):
    • C/C++ language code design
    • Any binary tree => heap (concern): How to ensure that the subtree must be a large/small heap?
  • Design and implementation of heap
    • Storage structure design
    • initialize heap
    • Insert data (involving expansion)
    • Heap destruction
    • Determine whether the heap is empty
    • Get the top element of the heap
    • Delete elements (note)
    • Get the number of elements in the heap
  • Conclusion

Understanding of complete binary trees

  • The definition of a complete binary tree: A binary tree with n nodes is numbered in hierarchical order. If the number is i (1 <= i <= n) and the node number i in a full binary tree of the same depth is in the binary tree, If the positions are exactly the same, this binary tree is called a complete binary tree.
  • A simple understanding of a complete binary tree (characteristics described in vernacular): Except for the bottom layer, all other layers are full of nodes (constituting a full binary tree). The bottom layer must satisfy a binary tree that does not contain empty leaf nodes from left to right!

Basic understanding of heap

  • Heap is a special type of data structure in computer science and is the most efficient priority queue.
  • The heap is usually an array of objects that can be viewed as a complete binary tree.

The second line of formula in the above picture describes: The characteristics of the heap: the value of a node in the heap is always no greater than or no less than the value of its parent node!

The properties of the heap and the size of the root heap [Important]

  • The value of a node in the heap is always not greater than or not less than the value of its parent node!

  • The heap is always a complete binary tree!

  • Big root heap: that is, the root node has the largest value!

  • Small root heap: that is, the root node has the smallest value!

The structure of the heap and its sequential structure (features)

Understanding the structure of the heap

  • Logically, one of the properties of a heap is that the heap must be a complete binary tree!
  • In terms of storage structure, due to the hierarchical “arrangement characteristics” of a complete binary tree, we generally use arrays or other sequential storage structures as storage objects to simulate a heap!

Sequential storage structure

From the graphical structure of complete binary numbers, it is not difficult to see that if we traverse them in layer order and arrange them in a row, we can form an array structure that does not contain empty nodes (numeric values)!

As shown in the figure above, stores the root node at the index value: 0! (has the following characteristics!)

If the node with index i has left and right child nodes, then:

  • Left subtree node index: 2 * i + 1
  • Right subtree node index: 2 * i + 2

If it is known that: the index value of the left/right child node is: n, then:

  • The parent node index is: (n-1) / 2

Upward adjustment algorithm

Basic idea of the algorithm (taking small root heap as an example):

  1. Find the node that does not conform to the heap properties! Recorded as: target node! As shown in the picture above: 0.
  2. Compare the values of the target node and its parent node!
  • If the target node value is less than the value of the parent node, parent-child exchange is performed!
  • If the value of the target node is greater than the value of its parent node, the upward adjustment will stop. At this time, the tree is already a small heap.

As shown above, the process description:

  • The first time, 0 < 8, exchange 0 and 8. At this time, the original 8 position is the original target value!
  • The second time, 0 < 4, swap 0 and 4,
    …
    As shown in the figure above, the target value 0 must be adjusted upward to the root node position of the entire tree!

How to confirm index value in exchange:

  • If it is known that: the index value of the left/right child node is: n, then:
    • The parent node index is: (n-1) / 2

C/C++ language code design

  • Since there is no container in the C language, we need to dynamically apply for a piece of memory as an array to store our data elements (the dynamic memory application part will be implemented later).
  • C++ can directly use vector as a container to store data.
void Swap(DataType* x, DataType* y)
{<!-- -->
DataType tmp = *x;
*x = *y;
*y = tmp;
}

/* Adjust algorithm upward */
// void AdjustUp(vector<DataType> & amp; vec, int idx) // C++
void AdjustUp(DataType* vec, int idx)
{<!-- -->
int parent = (idx-1) / 2; // Record the position of the parent node of the current node!
while(idx > 0){<!-- -->
// Loop condition: The position of the target node must be legal!
// Note: When the target node index is 1 or 2, if an exchange occurs, it will definitely be adjusted to 0!
// Take the small root heap as an example: Features: The father is smaller than the son!
if( vec[idx] < vec[parent] ){<!-- -->
Swap( & amp;vec[idx], & amp;vec[parent]); // Value exchange
idx = parent; // Update the index of the target value!
parent = (idx-1) / 2; // Update the index of the parent node!
}else break;
}
}

Downward adjustment algorithm

Basic idea of the algorithm (taking the big root heap as an example):

Downward adjustment algorithm needs to meet a prerequisite:
?If you want to adjust it to a small heap, then the left and right subtrees of the root node must both be small heaps.
?If you want to adjust it to a large heap, then the left and right subtrees of the root node must both be large heaps.

  1. Find the node that does not conform to the heap properties! Recorded as: target node! As shown in the picture above: 20.
  2. Compare the values of the target node and its larger child node! (Large root heap); Compare the values of the target node and its smaller child node! (small root pile).
  3. Taking the large root heap as an example, if the target node value (parent) is less than the value of the larger child node, parent-child exchange will be performed!

Using the downward adjustment algorithm of the heap, in the worst case (that is, nodes need to be exchanged all the time), the number of loops required is: h – 1 (h is the height of the tree). And h = log2(N + 1) (N is the number of summary points of the tree). Therefore, the time complexity of the heap downward adjustment algorithm is: O(logN).

As shown above, the process description:

  • The first time, 9 < 36, the maximum value is: 36! 20 < 36, exchange 20 and 36. At this time, the original 36 position is the original target value!
  • The second time, -54 < 10, the maximum value is: 10! 20 > 10, the adjustment is over!

How to confirm index value in exchange:

  • If it is known that: the index value of the parent node is: n, then:
    • Left subtree node index: 2 * n + 1
    • Right subtree node index: 2 * n + 2

C/C++ language code design

void Swap(DataType* x, DataType* y)
{<!-- -->
DataType tmp = *x;
*x = *y;
*y = tmp;
}

/* Downward adjustment algorithm: large root heap */
// void AdjustUp(vector<DataType> & amp; vec, int size, int idx) // C++
// Parameters: size: size of the array
void AdjustDown(DataType* vec, int size, int idx){<!-- -->
int child = idx*2 + 1; // child represents the subtree index!
// It is assumed here that the larger value is: left child node
while( child < size ){<!-- -->
// Determine the size relationship between the left and right child nodes
//Big root pile: choose the larger one
// Small root heap: choose the smaller one
if( child + 1 < size & amp; & amp; vec[child + 1] > vec[child] ) child + + ;
if(vec[idx] < vec[child]){<!-- -->
//Exchange the parent node with the larger child node
Swap( & amp;vec[child], & amp;vec[idx]);
//Continue to adjust downwards
idx=child;
child = 2 * idx + 1;
}else break;
}
}

Any binary tree => Heap (attention): How to ensure that the subtree must be a large/small heap?

There is a constraint in the previous downward adjustment algorithm!

Downward adjustment algorithm needs to meet a prerequisite:
?If you want to adjust it to a small heap, then the left and right subtrees of the root node must both be small heaps.
?If you want to adjust it to a large heap, then the left and right subtrees of the root node must both be large heaps.

Question: How to ensure that the subtree must be a large/small heap?

  • Due to the characteristics of the heap, the root node is either always smaller than the left and right child nodes, or always larger than the left and right child nodes! As long as any subtree meets this characteristic!
  • Implementation idea: Start from the penultimate subtree, that is, the parent node of the last node! Just adjust it downwards!

The figure below demonstrates adjusting to a small root heap as an example!

Code:

void ToHeap(DataType* vec, int size){<!-- -->
for(int i = (size - 1 - 1) / 2;i >= 0; i--)
AdjustDown(vec, size, i);
}

Design and implementation of heap

  • This article will use C design to implement a sequential storage heap!

Design of storage structure

Taking the C language as an example to make the heap applicable to more data types, we adopt the following design method!

//Type settings in the heap
typedef int DataType;

//Design of data type
typedef struct _Heap{<!-- -->
DataType* heapArray; // The underlying data storage relies on arrays
int size; // Record the number of elements in the current heap
int capacity; // Record the maximum number of elements that can be stored in the current stack! ! !
}Heap;

Initialize heap

  • The design idea here is: adjust the existing sequences into piles!

What needs to be done:

  • Memory application
  • data copy
  • Heap adjustment: any binary tree => heap
/*
Heap* heap: output parameter, build heap
DataType* vec: data sequence
*/
void InitHeap(Heap* heap, DataType* vec, int size){<!-- -->
assert(heap);
//Memory application
DataType* temp = (DataType*)malloc(sizeof(DataType)*size);
if(temp == NULL){<!-- -->
printf("malloc fail\
");
exit(-1);
}
//Initialization of heap structure
heap->heapArray = temp;
heap->size = size;
heap->capacity = size;

//data copy
memcpy(heap->heapArray, vec, sizeof(DataType)*size);

// Heap adjustment: any binary tree => heap
for(int i = (size-1-1)/2; i>=0;i--)
AdjustDown(heap->heapArray, size, i);
}

Insert data (involving capacity expansion)

Ideas for data insertion:

  • For arrays, the location for efficient data addition and deletion operations must be at the tail!
  • Data insertion strategy: Place the new element at the end of the array first! Then use the upward adjustment algorithm to adjust the heap!

Operating procedures:

  • Check the number of data elements in the heap (whether expansion is needed)
  • Heap adjustment (tail insertion data => upward adjustment algorithm)

About expansion:

In the initialization of the heap, we just applied for an array with the same size as the data source sequence to store data!

  • If there is no data insertion, the space utilization is the highest!
  • If data is inserted, expansion is required!

Conditions for expansion:

  • The number of data elements in the heap = the maximum number of elements that the heap can store

Regarding the expansion strategy: The main purpose of this article is to simulate the implementation of the heap, so the usage of space is not considered here!

  • The default expansion strategy is: 2x expansion!
void Insert(Heap* heap, DataType val){<!-- -->
assert(heap);
//Check whether to expand the capacity
if(heap->size == heap->capacity){<!-- -->
DataType* temp= (DataType*)realloc( heap->heapArray, 2 * (heap->capacity) * sizeof(DataType) );
if(temp == NULL){<!-- -->
printf("insert fail, may be realloc fail");
return;
}
heap->heapArray = temp;
heap->capacity *= 2;
}
heap->heapArray[heap->size] = val;
heap->size + + ;
AdjustUp(heap->heapArray, heap->size-1);
}

Heap destruction

Regarding the destruction of the heap, you only need to grasp that the memory requested for dynamic memory needs to be released using free. In order to prevent wild pointers from appearing, the pointers need to be made empty!

/Destroy the heap
void HeapDestroy(Heap* heap)
{<!-- -->
assert(heap);
free(heap->heapArray); //Release the dynamically opened array
php->a = NULL; //Prevent wild pointers from appearing
php->size = 0; //Set the number of elements to 0
php->capacity = 0; //Set capacity to 0
}

Determine whether the heap is empty

The key to whether the heap is empty: Whether the number of elements in the heap is: 0!
There is a bool type in subsequent versions of the C language, but in order to be more adaptable, we use the int type as the basis for judgment!

int IsEmpty(Heap* heap){<!-- -->
if(heap->size == 0) return 1; // Empty, return: 1
return 0; // Not empty, return: 0
}

Get the top element of the heap

Using an array as a storage container, the top element of the heap is naturally the root node, which is stored at the index: 0.
Note: Make sure the heap is not empty!

int HeapTop(Heap* heap){<!-- -->
// Only when it is not empty can there be a top of the heap!
assert(heap->size != 0);
return heap->heapArray[0];
}

Delete elements (notes)

be careful:

  • Heap deletion: refers to deleting the top element of the heap!
  • The prerequisite for deletion: there are elements!

Heap deletion strategy:

  • Swap the values of the top and bottom elements of the heap!
  • Adjust the exchanged value downward!
  • Modify the number of elements in the heap (size–)
void HeapDel(Heap* heap){<!-- -->
assert(heap);
assert(!IsEmpty(heap));
//Exchange element values: top element and tail element of the heap
Swap( & amp;heap->heapArray[0], & amp;heap->heapArray[size-1]);
heap->size--;
AdjustDown(heap->heapArray, heap->size, 0);
}

Get the number of elements in the heap

int HeapSize(Heap* heap){<!-- -->
return heap->size;
}

Conclusion

This article is just a simple design and implementation of heap-related operations! Heap application or algorithm questions will be updated in the future!