堆相关题目
一、实现大顶堆、小顶堆
1.1 小顶堆
/**
* @Date 2021/10/17
* @Author lifei
*/
public class MinHeap<T extends Comparable<T>> {
private int capacity;
private T[] a;
private int N;
public MinHeap(int capacity) {
this.capacity = capacity;
a = (T[]) new Comparable[capacity+1];
}
public int size() {
return N;
}
public boolean isEmpty() {
return size()==0;
}
public boolean isFull() {
return size()==capacity;
}
public void push(T t) {
if (isFull()) return;
a[++N] = t;
swim(N);
}
public T delMin() {
if (isEmpty()) return null;
T t = a[1];
exch(1, N--);
a[N+1] = null;
sink(1);
return t;
}
private void sink(int k) {
while (2*k<=N) {
int j = 2*k;
if (j<N && less(j+1, j)) j++;
if (less(k, j)) break;
exch(j, k);
k = j;
}
}
private void swim(int k) {
while (k>1 && less(k, k/2)) {
exch(k, k/2);
k = k/2;
}
}
private void exch(int i, int j) {
T t = a[i];
a[i] = a[j];
a[j] = t;
}
private boolean less(int i, int j) {
return a[i].compareTo(a[j])<0;
}
public static void main(String[] args) {
MinHeap<Integer> heap = new MinHeap<>(6);
heap.push(3);
heap.push(5);
heap.push(1);
heap.push(0);
heap.push(9);
heap.push(2);
while (!heap.isEmpty()) {
System.out.print(heap.delMin() + ", ");
}
System.out.println();
}
}
1.2 大顶堆
/**
* @Date 2021/10/17
* @Author lifei
*/
public class MaxHeap<T extends Comparable<T>> {
private int capacity;
private T[] a;
private int N;
public MaxHeap(int capacity) {
this.capacity = capacity;
a = (T[]) new Comparable[capacity+1];
}
public int size() {
return N;
}
public boolean isEmpty() {
return size()==0;
}
public boolean isFull() {
return size()==capacity;
}
public void push(T t) {
if (isFull()) return;
a[++N] = t;
swim(N);
}
public T delMax() {
if (isEmpty()) return null;
T t = a[1];
exch(1, N--);
a[N+1] = null;
sink(1);
return t;
}
private void sink(int k) {
while (2*k<=N) {
int j = 2*k;
if (j<N && less(j, j+1)) j++;
if (less(j, k)) break;
exch(j, k);
k = j;
}
}
private void swim(int k) {
while (k>1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
private void exch(int i, int j) {
T t = a[i];
a[i] = a[j];
a[j] = t;
}
private boolean less(int i, int j) {
return a[i].compareTo(a[j])<0;
}
public static void main(String[] args) {
MaxHeap<Integer> heap = new MaxHeap<>(6);
heap.push(3);
heap.push(5);
heap.push(1);
heap.push(0);
heap.push(9);
heap.push(2);
while (!heap.isEmpty()) {
System.out.print(heap.delMax() + ", ");
}
System.out.println();
}
}
二、堆排序
核心方法：sink
public class HeapSort {
public static void main(String[] args) {
Integer[] a = {9, 8,4, 1,2, 9, 8,4, 1,2};
System.out.println(Arrays.toString(a));
HeapSort.sort(a);
System.out.println(Arrays.toString(a));
}
public static void sort(Comparable[] a) {
if (a==null || a.length<=1) return;
int N = a.length;
for (int k=N/2; k>=1; k--) {
sink(a, k, N);
}
while (N>=1) {
exch(a, 1, N--);
sink(a, 1, N);
}
}
private static void sink(Comparable[] a, int k, int N) {
while (k*2<=N) {
int j = k*2;
if (j<N && less(a, j, j+1)) j++;
if (less(a, j, k)) break;
exch(a, k, j);
k = j;
}
}
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i-1];
a[i-1] = a[j-1];
a[j-1] = t;
}
private static boolean less(Comparable[] a, int i, int j) {
return a[i-1].compareTo(a[j-1])<0;
}
}
3.1 解法一：排序后取值
public int[] getLeastNumbers(int[] arr, int k) {
Arrays.sort(arr);
int[] res = new int[k];
for (int i=0; i<k; i++) {
res[i] = arr[i];
}
return res;
}
3.2 解法二：借助堆排序解决
public int[] getLeastNumbers(int[] arr, int k) {
int N = arr.length;
if (N<1) return new int[0];
for (int i=N/2; i>=1; i--) {
sink(arr, i, N);
}
int[] res = new int[k];
int j = 0;
while (j<k) {
res[j++] = arr[0];
exch(arr, 1, N--);
sink(arr, 1, N);
}
return res;
}
private void sink(int[] arr, int k, int N) {
while (k*2<=N) {
int j = k * 2;
if (j<N && less(arr, j+1, j)) j++;
if (less(arr, k, j)) break;
exch(arr, j, k);
k = j;
}
}
private boolean less(int[] arr, int i, int j) {
return arr[i-1]<arr[j-1];
}
private void exch(int[] arr, int i, int j) {
int t = arr[i-1];
arr[i-1] = arr[j-1];
arr[j-1] = t;
}
还是使用队列比较好做
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length-k+1];
for (int i=0; i<nums.length; i++) {
while (!deque.isEmpty() && nums[deque.peekLast()]<nums[i]) {
deque.removeLast();
}
deque.addLast(i);
int w = i - k + 1;
if (deque.peek()<w) {
deque.pop();
}
if (w>=0) {
res[w] = nums[deque.peek()];
}
}
return res;
}
解法一：使用优先级队列和Set
public int nthUglyNumber(int n) {
int[] a = {2, 3, 5};
PriorityQueue<Long> queue = new PriorityQueue<>();
Set<Long> visited = new HashSet<>();
queue.add(1l);
visited.add(1l);
long res = 1;
for (int i=1; i<=n; i++) {
res = queue.poll();
for (int k=0; k<a.length; k++) {
if (!visited.contains(a[k]*res)) {
visited.add(a[k]*res);
queue.add(a[k]*res);
}
}
}
return (int)res;
}
解法二：动态规划
public int nthUglyNumber(int n) {
int[] dp = new int[n+1];
dp[1]= 1;
int p2 = 1, p3 = 1, p5 = 1;
for (int i=2; i<=n; i++) {
int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
dp[i] = Math.min(Math.min(num2, num3), num5);
// 解决重复问题
if (dp[i]==num2) {
p2++;
}
if (dp[i]==num3) {
p3++;
}
if (dp[i]==num5){
p5++;
}
}
return dp[n];
}
6.1 解法一：使用大顶堆，sink、swim
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map =new HashMap<>();
for (int i=0; i<nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
}
int[] a = new int[map.size()+1];
int N = 0;
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
a[++N] = entry.getKey();
swim(a, N, map);
}
int[] res = new int[k];
for (int i=0; i<k; i++) {
res[i] = a[1];
exch(a, 1, N--);
sink(a, 1, N, map);
}
return res;
}
private void sink(int[] a, int k, int N, Map<Integer, Integer> map) {
while (k*2<=N) {
int j= k * 2;
if (j<N && less(j, j+1, map, a)) j++;
if (less(j, k, map, a)) break;
exch(a, j, k);
k = j;
}
}
private void swim(int[] a, int k, Map<Integer, Integer> map) {
while (k>1 && less(k/2, k, map, a)) {
exch(a, k, k/2);
k = k/2;
}
}
private void exch(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
private boolean less(int i, int j, Map<Integer, Integer> map, int[] a) {
return map.get(a[i])<map.get(a[j]);
}
|