# I. Preface

A heap is an array that can be seen as an approximate complete binary tree. The array representing the heap includes two attributes: A.length the number of array elements, and A.heapSize the number of elements in the array. The relationship here is:

``` 0<= A.heapSize<=A.length
```

The root node of the tree is A[1], and the time complexity of heap sorting is O(nlgn). Binary heap can be divided into two types: maximum heap and minimum heap. The maximum heap is parent > = child. The smallest heap is the opposite. Next, use java to realize the maximum heap, mainly refer to the introduction of algorithm.

# 2, Maximum heap implementation

Since the array does not have heapSize, you need to deal with it yourself.

```public class HeapSort {

public static void main(String[] args) {
HeapSort hs = new HeapSort();
// The - 1 here is not an element in the heap, just let the array count from 1
int a[] = { -1, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
int heapSize = a.length - 1;
hs.build_max_heap(a);
hs.heapSort(a);
hs.heapExtractMax(a, heapSize);
hs.print(a);
}

/**
* Take out the maximum value
*/
public int heapMaximum(int[] a) {
return a[1];
}

/**
* Takes the value of the largest element and takes it from the array
*/
public int heapExtractMax(int a[], int heapSize) {
if (heapSize < 1) {
throw new RuntimeException("heap underflow");
}
int max = a[1];
a[1] = a[heapSize];
heapSize = heapSize - 1;
max_heapify(a, 1, heapSize);
return max;
}

/**
* Increase the value of a node
*/
public void heapIncreaseKey(int[] a, int i, int key) {
if (key < a[i]) {
throw new RuntimeException("new key is smaller than current key");
}
a[i] = key;
while (i > 1 && a[parent(i)] < a[i]) {
swap(a, i, parent(i));
i = parent(i);
}

}

/**
* Insertion element
*/
public void maxHeapInsert(int[] a, int key, int heapSize) {
heapSize = heapSize + 1;
a[heapSize] = 0;
heapIncreaseKey(a, heapSize, key);
}

/**
* Heap sort
*/
public void heapSort(int a[]) {
build_max_heap(a);
int len = a.length - 1;
for (int i = len; i >= 2; i--) {
swap(a, 1, i);
len = len - 1;
max_heapify(a, 1, len);
}

print(a);
}

/**
* Build maximum heap
*/
public void build_max_heap(int[] a) {
int i = a.length / 2;
int heap_size = a.length - 1;
for (; i >= 1; i--) {
max_heapify(a, i, heap_size);
}
}

/**
* For tree height h, time complexity O(h)
*/
public void max_heapify(int[] a, int i, int heap_size) {
int l = left(i);
int r = right(i);
int largest;
if (l <= heap_size && a[l] > a[i]) {
largest = l;
} else {
largest = i;
}

if (r <= heap_size && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
swap(a, largest, i);
max_heapify(a, largest, heap_size);
}
}
/**
*  Parent node
*/
public int parent(int i) {
return i / 2;
}
/**
*  Left child
*/
public int left(int i) {
return 2 * i;
}
/**
*  Right child
*/
public int right(int i) {
return 2 * i + 1;
}
/**
*  Exchange the values of two elements in an array
*/
public void swap(int a[], int x, int y) {
try {
int t = a[x];
a[x] = a[y];
a[y] = t;
} catch (Exception e) {
e.printStackTrace();
System.out.println("x:" + x + ";y:" + y);
}
}

/**
* Printing
*/
public void print(int[] a) {
for (int i : a) {
System.out.println("a=>" + i);
}
}

}```

# Three, summary

In general, heap sorting is very simple, and what has been written in the introduction of algorithm is very clear. I bought this book when I was a junior. I didn't read it very much at that time. Now I want to read it again. It's a classic after all. I hope I can keep reading it. Internal skill strengthening~~~~~

Reference: introduction to algorithm

Tags: Java

Posted on Sun, 05 Apr 2020 13:06:38 -0700 by Darkness31