Heapify
Heapify
้ข็ฎๅฐๅ
https://www.lintcode.com/problem/heapify
้ข็ฎๆ่ฟฐ
Given an integer array, heapify it into a min-heap array.
For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].
ไปฃ็
public class Solution {
public void heapify(int[] nums {
for (int i = nums.length / 2; i >= 0; i--) {
minheap(nums, i);
}
}
private void minheap(int[] nums, int k) {
int n = nums.length;
while (k < n) {
int minIndex = k;
int left = k * 2 + 1;
int right = k * 2 + 2;
if (left < n && nums[left] < nums[minIndex]) {
minIndex = left;
}
if (right < n && nums[right] < nums[minIndex]) {
minIndex = right;
}
if (k == minIndex) break;
int temp = nums[k];
nums[k] = nums[minIndex];
nums[minIndex] = temp;
k = minIndex;
}
}
}
Approach 2:
public class Solution {
public void heapify(int nums) {
for (int i = 0; i < nums.length; i++) {
siftup(nums, i);
}
}
private void siftup(int[] nums, int k) {
while (k != 0) {
int father = (k - 1) / 2;
if (nums[k] > nums[father]) {
break;
}
int temp = nums[k];
nums[k] = nums[father];
nums[father] = temp;
k = father;
}
}
}
Last updated