I still believe that what Hamming did in coding theory and the Reed-Solomon codes, etc., are 'basic' and new since computers.
But, you are correct that transmission error detection and correction were old needs with old solutions. E.g., there was parity with teletypewriters and old paper tape for error detection and then retransmission for error correction. Yes, and the improvements Hamming, etc., made for computers were not feasible before computers, but I still believe that, while the problem was old and had old solutions, the work of Hamming, etc. was new and 'basic'.
Yes, heap sort doesn't really work as a sorting technique before computers, but trying to dream up heap sort is not easy -- just for the heck of it, once I set aside reading how heap sort worked and tried to dream up such a thing for about two weeks and couldn't do it. Heap sort's darned clever.