Is the bitstream for the decoder a lot more complex?
From what I recall (and it has been a few years), usually the standard mostly specifies what the 'end product' will look like and the encoders basically have to figure out a way to get there. The decoding was usually pretty expensive and had a lot of quality options and was constantly trying to detect things like global motion compensation etc, while the decoder basically just decoded the same old bitstream without a lot of change in complexity for the same profile level.
Also expensive is using CABAC, which is much slower (for better compression ratio). H.264 allowed used a faster coder called CAVLC.
There are two ways to interpret this: either low-powered devices have become much stronger, or h.264 is just not supporting some classes of devices.
I believe CABAC in h265/HEVC should be faster than CABAC in h264/AVC. If you produced CABAC for h264 and h265 with all things being equal you should actually gain in decoding speed moving to h265.
That said, if you actually get the standard and look at the section on the intra prediction modes, how to compute them is spelled out in very detailed pseudocode.