355. Design Twitter

import (
	"container/heap"
)

type tweet struct {
	time int
	id   int
}

type tweetPair struct {
	userID     int
	tweetIndex int
	value      tweet
}

type feedHeap []*tweetPair

func (heapSlice feedHeap) Len() int { return len(heapSlice) }
func (heapSlice feedHeap) Less(left, right int) bool {
	return heapSlice[left].value.time > heapSlice[right].value.time
}
func (heapSlice feedHeap) Swap(left, right int) {
	heapSlice[left], heapSlice[right] = heapSlice[right], heapSlice[left]
}

func (heapSlice *feedHeap) Push(value any) {
	*heapSlice = append(*heapSlice, value.(*tweetPair))
}

func (heapSlice *feedHeap) Pop() any {
	old := *heapSlice
	length := len(old)
	item := old[length-1]
	*heapSlice = old[0 : length-1]
	return item
}

type Twitter struct {
	time        int
	tweets      map[int][]tweet
	following   map[int]map[int]struct{}
}

func Constructor() Twitter {
	return Twitter{
		tweets:    make(map[int][]tweet),
		following: make(map[int]map[int]struct{}),
	}
}

func (receiver *Twitter) PostTweet(userID int, tweetID int) {
	receiver.time++
	receiver.tweets[userID] = append(receiver.tweets[userID], tweet{time: receiver.time, id: tweetID})
}

func (receiver *Twitter) GetNewsFeed(userID int) []int {
	maxHeap := &feedHeap{}
	heap.Init(maxHeap)
	if list, ok := receiver.tweets[userID]; ok && len(list) > 0 {
		end := len(list) - 1
		heap.Push(maxHeap, &tweetPair{userID: userID, tweetIndex: end, value: list[end]})
	}
	if followSet, ok := receiver.following[userID]; ok {
		for followeeID := range followSet {
			if list, has := receiver.tweets[followeeID]; has && len(list) > 0 {
				end := len(list) - 1
				heap.Push(maxHeap, &tweetPair{userID: followeeID, tweetIndex: end, value: list[end]})
			}
		}
	}
	const limit = 10
	result := make([]int, 0, limit)
	for maxHeap.Len() > 0 && len(result) < limit {
		top := heap.Pop(maxHeap).(*tweetPair)
		result = append(result, top.value.id)
		if top.tweetIndex > 0 {
			u := top.userID
			list := receiver.tweets[u]
			nextIndex := top.tweetIndex - 1
			heap.Push(maxHeap, &tweetPair{userID: u, tweetIndex: nextIndex, value: list[nextIndex]})
		}
	}
	return result
}

func (receiver *Twitter) Follow(followerID int, followeeID int) {
	if _, ok := receiver.following[followerID]; !ok {
		receiver.following[followerID] = make(map[int]struct{})
	}
	receiver.following[followerID][followeeID] = struct{}{}
}

func (receiver *Twitter) Unfollow(followerID int, followeeID int) {
	if set, ok := receiver.following[followerID]; ok {
		delete(set, followeeID)
	}
}

class MaxHeap {
  constructor(compare) {
    this.data = [];
    this.compare = compare;
  }

  size() {
    return this.data.length;
  }

  push(item) {
    this.data.push(item);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(this.data[index], this.data[parentIndex]) <= 0) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const leftChild = index * 2 + 1;
      const rightChild = index * 2 + 2;
      let largest = index;
      if (leftChild < length && this.compare(this.data[leftChild], this.data[largest]) > 0) {
        largest = leftChild;
      }
      if (rightChild < length && this.compare(this.data[rightChild], this.data[largest]) > 0) {
        largest = rightChild;
      }
      if (largest === index) {
        break;
      }
      this.swap(index, largest);
      index = largest;
    }
  }

  swap(leftIndex, rightIndex) {
    const temp = this.data[leftIndex];
    this.data[leftIndex] = this.data[rightIndex];
    this.data[rightIndex] = temp;
  }
}

class Twitter {
  constructor() {
    this.time = 0;
    this.tweets = new Map();
    this.following = new Map();
  }

  postTweet(userId, tweetId) {
    this.time += 1;
    if (!this.tweets.has(userId)) {
      this.tweets.set(userId, []);
    }
    this.tweets.get(userId).push({ time: this.time, id: tweetId });
  }

  getNewsFeed(userId) {
    const heap = new MaxHeap((left, right) => left.value.time - right.value.time);
    const pushLatest = (accountId) => {
      const list = this.tweets.get(accountId);
      if (!list || list.length === 0) {
        return;
      }
      const index = list.length - 1;
      heap.push({ accountId, index, value: list[index] });
    };
    pushLatest(userId);
    const seen = this.following.get(userId);
    if (seen) {
      for (const followeeId of seen.keys()) {
        pushLatest(followeeId);
      }
    }
    const result = [];
    const limit = 10;
    while (heap.size() > 0 && result.length < limit) {
      const top = heap.pop();
      result.push(top.value.id);
      if (top.index > 0) {
        const list = this.tweets.get(top.accountId);
        const nextIndex = top.index - 1;
        heap.push({ accountId: top.accountId, index: nextIndex, value: list[nextIndex] });
      }
    }
    return result;
  }

  follow(followerId, followeeId) {
    if (!this.following.has(followerId)) {
      this.following.set(followerId, new Map());
    }
    this.following.get(followerId).set(followeeId, true);
  }

  unfollow(followerId, followeeId) {
    const inner = this.following.get(followerId);
    if (inner) {
      inner.delete(followeeId);
    }
  }
}