There are two ways to implement the maximum/small heap using Array[0]. One way is to use Array[0] with no actual value, and the other way is to use Array[0] with actual value. In the first case, the length of the array is one more than the number of nodes in the heap, because there are no nodes in [0]. For the left and right children of I, there are 2i and 2i + 1, and the parent is (I – 1)/2. In the second case, the length of the array is equal to the number of nodes in the heap, since [0] is the root node, and the left and right children of I are 2i + 1 and 2i + 2, and the parent node is I /2. Let’s take the maximum heap for example;
C language to achieve the first:
#include <stdio.h> #include <stdlib.h> typedef struct MaxHeap { int *data; // data field int size; // Length int Max; // Maximum length} maxHeap; Void insert(struct MaxHeap *p, int item){if (p->size == p-> Max){printf(":\n"); return; } int i = ++p->size; // add 1 to int, so that the first index inserted into the array is 1 for (; p->data[i/2] < item; If (I <= 1) {if (I <= 1) {break; } p->data[i] = p->data[i/2]; } p->data[i] = item; } // void void (struct MaxHeap *p){p->data[1] = p->data[p->size--]; int i = 1; int tmp; While (2 * I < = p - > size) {/ / if you have the right node if (2 * I + 1 < = p - > size) {if (p - > data (2 * I + 1) > p - > data [I] | | p - > data [I] 2 * > p->data[i]) { if (p->data[2*i + 1] > p->data[2*i]) { tmp = p->data[i]; p->data[i] = p->data[2*i + 1]; p->data[2*i + 1] = tmp; i = 2*i + 1; }else{ tmp = p->data[i]; p->data[i] = p->data[2*i]; p->data[2*i] = tmp; i = 2*i; } }else{ return; }} else {/ / only if the left node (p - > data [I] 2 * > p - > data [I]) {TMP = p - > data [I]; p->data[i] = p->data[2*i]; p->data[2*i] = tmp; i = 2*i; }else{ return; }}}} // void TraverseArray(struct MaxHeap *p) {if (p! = NULL) { printf("size:%d \n",p->size); for (int i = 1; i <= p->size; ++i) { printf("%d \n",p->data[i]); }}} // void checkMaxHeap(struct maxHeap *p) {if (p! = NULL) { for (int i = 1; i <= p->size; ++i) { if (2*i <= p->size) { if (p->data[i] < p->data[2*i]) { printf("error l %d \n",i); } } if (2*i +1 <= p->size) { if (p->data[i] < p->data[2*i +1]) { printf("error r %d \n",i); for (int j = 0; j <= 2*i +1; ++j) { printf("error r: %d \n",p->data[j]); } return; } } } } }C language to achieve the second:
#include <stdio.h> #include <stdlib.h> typedef struct MaxHeap { int *data; // data field int size; // Length int Max; // Maximum length} maxHeap; void TraverseArray(struct MaxHeap *p) { if (p ! = NULL) { printf("size:%d \n",p->size); for (int i = 0; i < p->size; ++i) { printf("%d \n",p->data[i]); } } } void insert(struct MaxHeap *p, int item){ if (p->size == p->max) { printf("******:\n"); return; } int i = p->size++; for (; i > 0 && p->data[(i-1)/2] < item; i=(i-1)/2) { if (i < 1) { break; } p->data[i] = p->data[(i-1)/2]; } p->data[i] = item; } void delete(struct MaxHeap *p){ p->data[0] = p->data[--p->size]; int i = 0; int tmp = 0; While (2 * I + 1 < p > size) {/ / if you have the right node if I + (2 * 2 < p - > size) {if (p - > data [I + 2 * 2] > p - > data [I] | | p - > data (2 * I + 1) > p->data[i]) { if (p->data[2*i + 2] > p->data[2*i + 1]) { printf("dele r max :%d \n",i); tmp = p->data[i]; p->data[i] = p->data[2*i + 2]; p->data[2*i + 2] = tmp; i = 2*i + 2; }else{ printf("dele l max :%d \n",i); tmp = p->data[i]; p->data[i] = p->data[2*i + 1]; p->data[2*i + 1] = tmp; i = 2*i + 1; } }else{ return; }} else {/ / only if the left node (p - > data (2 * I + 1) > p - > data [I]) {TMP = p - > data [I]; p->data[i] = p->data[2*i + 1]; p->data[2*i + 1] = tmp; i = 2*i + 1; }else{ return; } } } } void checkMaxHeap(struct MaxHeap *p) { if (p ! = NULL) { for (int i = 1; i <= p->size; ++i) { if (2*i <= p->size) { if (p->data[i] < p->data[2*i + 1]) { printf("error l %d \n",i); } } if (2*i +1 <= p->size) { if (p->data[i] < p->data[2*i +1]) { printf("error r %d \n",i); for (int j = 0; j <= 2*i +1; ++j) { printf("error r: %d \n",p->data[j]); } return; } } } } }