// push down heap element data[index] in data[0..end] // array index start with 0 instead of 1 in CLR void max_heapify(vector<int> &data, int end, int curr_root) { int left_child_idx = curr_root * 2 + 1; int right_child_idx = curr_root * 2 + 2; int largest_index = curr_root; if(left_child_idx <= end && data[largest_index] < data[left_child_idx]) largest_index = left_child_idx; if(right_child_idx <= end && data[largest_index] < data[right_child_idx]) largest_index = right_child_idx; if(largest_index != curr_root) { std::swap(data[largest_index], data[curr_root]); max_heapify(data, end, largest_index); } }
/*
index >= size/2 are all leaves, because the child index (size/2 * 2 + 1) is out of bound,
so we can start build heap from the leave nodes
*/
// make array data[0..end] into a heap void build_heap(vector<int> &data, int end) { for(int idx = data.size() / 2; idx >= 0; --idx) max_heapify(data, end, idx); } // 0) heap_size = data.size() - 1; // 1) make array data[0..heap_size] into a heap // 2) swap data[0] (max element) to the end // 3) decrease heap size by 1 // 4) goto 1) void heapsort(vector<int> &data) { int heap_size = data.size() - 1; build_heap(data, heap_size); for(int idx = data.size()-1; idx >= 1; --idx) { std::swap(data[0], data[idx]); heap_size--; max_heapify(data, heap_size, 0); } }
