package main import ( 'fmt' 'math' 'strconv' 'strings' ) type MyHeap struct { data []int len int } func ScanLine() string { var c byte var err error var b []byt ..

Heap_OJ

package main

import (
	"fmt"
	"math"
	"strconv"
	"strings"
)

type MyHeap struct {
	data []int
	len  int
}

func ScanLine() string {
	var c byte
	var err error
	var b []byte
	for err == nil {
		_, err = fmt.Scanf("%c", &c)

		if c != '\n' {
			b = append(b, c)
		} else {
			break
		}
	}

	return string(b)
}

func strToInt(input string) []int {
	strs := strings.Split(input, " ")
	ret := make([]int, len(strs))
	for index, value := range strs {
		num, err := strconv.Atoi(value)
		if err != nil {
			fmt.Println(err)
			return nil
		}
		ret[index] = num
	}
	return ret
}

func MyHeapInit() *MyHeap {
	return &MyHeap{make([]int, 1, 10), 0}

}

func (h *MyHeap) getMinIndex(a, b int) int {
	if h.data[a] < h.data[b] {
		return a
	}
	return b
}

func (h *MyHeap) Add(input int) {
	h.data = append(h.data, input)
	h.len++
	h.up(h.len)
}

func (h *MyHeap) down(index int) {
	k := index
	for {
		childLeft := k * 2
		childRight := k*2 + 1
		if childLeft > h.len {
			return
		}
		minIndex := h.getMinIndex(k, childLeft)
		if childRight <= h.len {
			minIndex = h.getMinIndex(minIndex, childRight)
		}
		if minIndex == k {
			return
		}
		h.data[k], h.data[minIndex] = h.data[minIndex], h.data[k]
		k = minIndex
	}
}

func (h *MyHeap) up(index int) {
	k := index
	for {
		parent := k / 2
		if parent == 0 {
			return
		}
		if h.data[k] < h.data[parent] {
			h.data[k], h.data[parent] = h.data[parent], h.data[k]
			k = parent
		} else {
			return
		}
	}
}

func (h *MyHeap) Delete(input int) {
	destIndex := 0
	for index, value := range h.data {
		if value == input {
			destIndex = index
			h.data[h.len], h.data[destIndex] = h.data[destIndex], h.data[h.len]
			h.len--
			h.data = h.data[:h.len+1]
			break
		}
	}

	if destIndex == 0 {
		return
	}

	parent := destIndex / 2
	if parent != 0 && h.data[destIndex] < h.data[parent] {
		h.up(destIndex)

		return
	}
	h.down(destIndex)
}

func (h *MyHeap) Print() {
	if h.len == 0 {
		fmt.Println(" ")
		fmt.Println()
		return
	}
	heigth := int(math.Log2(float64(h.len)) + 1)
	j := 0
	for l := 1; l < heigth; l++ {
		for j = int(math.Pow(2, float64(l-1))); j < int(math.Pow(2, float64(l)))-1; j++ {
			fmt.Printf("%d ", h.data[j])
		}
		fmt.Printf("%d\n", h.data[j])
	}
	for j = int(math.Pow(2, float64(heigth-1))); j < h.len; j++ {
		fmt.Printf("%d ", h.data[j])
	}
	fmt.Printf("%d\n", h.data[j])

}

func (h *MyHeap) getValue(index int) int {
	if index < 0 || index > h.len {
		return -1
	}
	return h.data[index]
}

func main() {
	var n, m int
	tmp := strToInt(ScanLine())
	n = tmp[0]
	m = tmp[1]
	tmp = strToInt(ScanLine())
	h := MyHeapInit()
	for i := 0; i < n; i++ {
		h.Add(tmp[i])
	}
	for i := 0; i < m; i++ {
		tmpm := ScanLine()
		tmpm2 := strings.Split(tmpm, " ")
		value, _ := strconv.Atoi(tmpm2[1])
		if tmpm2[0] == "add" {
			h.Add(value)
		} else if tmpm2[0] == "delete" {
			h.Delete(value)
		}
		h.Print()

	}
}

  • golang

    Go 语言是 Google 推出的一种全新的编程语言,可以在不损失应用程序性能的情况下降低代码的复杂性。谷歌首席软件工程师罗布派克(Rob Pike)说:我们之所以开发 Go,是因为过去 10 多年间软件开发的难度令人沮丧。Go 是谷歌 2009 发布的第二款编程语言。

    336 引用 • 1180 回帖 • 722 关注
  • oj
    2 引用
回帖
请输入回帖内容...