手写堆.md

小顶堆（Go）

建堆有两种方式：

1. 自顶向下，从第一个节点开始到最后一个节点遍历，按插入节点的方式建堆，节点的交换是从下往上的，时间复杂度是 O(nlogn)
2. 自底向上，从倒数第一个非叶子节点开始，到第一个节点，节点的交换是从上往下的，时间复杂度是 O(n)

堆的操作：

1. 插入节点：将节点插入到数组尾，用将数组的尾节点从下往上的交换方式一直往上交换

2. 弹出堆顶：交换堆顶节点和数组最后一个节点，删除数组最后一个节点，接着将堆顶节点用从上往下的方式一直往下交换

package main

import "fmt"

func main() {
	h := heap{4, 6, 9, 1, 2, 3, 12, 34, 5, 6}
	h.init1()
	fmt.Println(h)
	h.insert(0)
	fmt.Println(h)
	h.pop()
	fmt.Println(h)
}

type heap []int

func (h heap) swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h heap) init1() { // bottom-up, O(n), 自底向上的建堆方式，节点的交换是从上往下的
	for i := len(h)/2 - 1; i >= 0; i-- {
		h.topDown(i)
	}
}

func (h heap) init2() { // top-down O(nlogn) 自顶向下的建堆方式，节点的交换是从下往上的
	for i := 0; i < len(h); i++ {
		h.bottomUp(i)
	}
}

func (h *heap) insert(val int) {
	*h = append(*h, val)
	h.bottomUp(len(*h) - 1)
}

func (h heap) bottomUp(cur int) {
	parent := (cur+1)/2 - 1
	for parent >= 0 {
		if h[cur] < h[parent] {
			h.swap(cur, parent)
		} else {
			break
		}
		cur = parent
		parent = (parent+1)/2 - 1
	}
}

func (h heap) topDown(cur int) {
	minn := 2*cur + 1
	for minn < len(h) {
		if 2*cur+2 < len(h) && h[2*cur+2] < h[minn] {
			minn = 2*cur + 2
		}
		if h[cur] > h[minn] {
			h.swap(cur, minn)
		} else {
			break
		}
		cur = minn
		minn = 2*cur + 1
	}
}

func (h *heap) pop() int {
	h.swap(0, len(*h)-1)
	res := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	h.topDown(0)
	return res
}

大顶堆（Java）

从第一个非叶子节点（若数组长度为 size，那么第一个非叶子节点的下标则为 size / 2 ）倒序遍历至第一个节点，每个循环中都与自身子节点中较大的子节点交换。

package src.DataStructure;

public class Heap {

    private int[] arrays = new int[1000];

    private int size;

    public Heap(int[] arrays){
        this.size = arrays.length;
        System.arraycopy(arrays, 0, this.arrays, 0, size);
        heapify(size);
    }

    public void add(int value){
        arrays[size++] = value;
        heapify(size);
    }


    public void heapify(int size){
        for(int i = size / 2; i >= 0; i--){
            sink(i);
        }
    }

    public void sink(int index){
        while(2 * index + 1 < size){
            int temp = 2 * index + 1;
            if(temp + 1 < size && arrays[temp] < arrays[temp + 1]){
                temp = temp + 1;
            }
            if(arrays[temp] <= arrays[index]){
                break;
            }
            swap(arrays, index, temp);
            index = temp;
        }
    }

    public int poll(){
        int ans = arrays[0];
        swap(arrays, 0, --size);
        heapify(size);
        return ans;
    }

    public void swap(int[] nums, int left, int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }


    public static void main(String[] args) {
        int[] arrays = new int[]{6, 8, 10, 2, 4, 11, 13, 9, 1, 5, 7, 3};
        Heap heap = new Heap(arrays);
        heap.add(200);
        while(heap.size != 0){
            System.out.println(heap.poll());
        }
    }
}