编辑代码

#include <iostream>
#include <cmath>

using namespace std;

class HeapFromBottom {
	private:
		int *heap;
		int capacity;
		
		void heapify(int nodeIndex, int heapBottom) {
			
			int lastParentIndex = floor(heapBottom/2);
			
			while (nodeIndex <= lastParentIndex) {
				
				// 找出左右子节点里面值较大的索引 
				int leftChildIndex = 2 * nodeIndex;
					
				int maxIndex = leftChildIndex;
				
				if((leftChildIndex + 1 <= heapBottom)
				&& (heap[leftChildIndex + 1] > heap[leftChildIndex])) {
					maxIndex = leftChildIndex + 1;
				}  
				
				// 让父亲节点和最大的节点比较 
				if (heap[nodeIndex] < heap[maxIndex]) {
					int temp = heap[nodeIndex] ;
					heap[nodeIndex] = heap[maxIndex];
					heap[maxIndex] = temp;
				     
					nodeIndex = maxIndex;	
				}
				else {
					break;
				}
				
			}
			
		}
		
	public:
		
		HeapFromBottom(int arr[], int length) {
			heap = new int(length + 1);
			capacity = length;
			
			for (int i = 0; i < length; ++i) {
				heap[i+1] = arr[i];
			}
			
			int lastParentIndex = floor(length/2);
			
			// 堆化 
			for (int i = lastParentIndex; i > 0; --i) {
				
				heapify(i, capacity);
			}
			
			
		}
		
		void sort() {
			int heapTop = 1;
			int heapBottom = capacity;
 
			
			// 只剩堆顶元素 
			while (heapTop < heapBottom) {
				
				// 堆顶和堆的最后一个元素交换,多了一个有序的元素
				int temp = heap[heapTop];
				heap[heapTop] = heap[heapBottom];
				heap[heapBottom] = temp; 
			
					
			   //对除去最后一个元素的堆进行堆化
			   --heapBottom;
			   
			   //堆化 
			   heapify(heapTop, heapBottom); 
			}
				
		}
		
		void print() {
			for (int i = 1; i < capacity + 1; ++i) {
				cout << heap[i] << " ";
			}
			cout << endl;
		}
};

int main() {
	int arr[] = {2, 9, 7, 6, 5, 8};
	
	HeapFromBottom *heap = new HeapFromBottom(arr, sizeof(arr)/sizeof(int));
	
	heap->print();
	heap->sort();
	heap->print();
	
	delete heap;
	
	return 0;
}