We design a new data structure, called a trinomial heap, which supports a decrease-key in O(1) time, and an insert operation and delete-min operation in O(log n) time, both in the worst case, where n is the size of the heap. The merit of the trinomial heap is that it is conceptually simpler and easier to implement than the previously invented relaxed heap. The relaxed heap is based on binary linking, while the trinomial heap is based on ternary linking.